2013年8月8日

UVa 11093 - Just Finish it up

#include <cstdio>

int main() {
  int T, C = 1;
  scanf("%d", &T);
  while (T--) {
    int N, p[100001], q[100001], sum[100001] = {};
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
      scanf("%d", &p[i]);
      if (i) {
        sum[i] = sum[i - 1] + p[i];
      } else {
        sum[i] = p[i];
      }
    }
    for (int i = 0; i < N; i++) {
      scanf("%d", &q[i]);
    }
    int start = 0, need = 0, minus = 0, available  = 0;
    for (int i = 0; i < N; i++) {
      need += q[i];
      available = sum[i] - minus;
      if (need > available) {
        need = 0;
        if (q[i] > p[i]) {
          start = i + 1;
          minus = sum[i];
        } else {
          start = i;
          minus = sum[i] - p[i];
          i--;
        }
      }
    }
    bool possible = need <= available;
    for (int i = 0; i < start && possible; i++) {
      need += q[i];
      available += p[i];
      if (need > available) {
        possible = false;
      }
    }
    printf("Case %d: ", C++);
    if (possible) {
      printf("Possible from station %d\n", start + 1);
    } else {
      puts("Not possible");
    }
  }
  return 0;
}

沒有留言:

張貼留言