oj.uz

Submission #31760

# Submission time Handle Problem Language Result Execution time Memory
31760 2017-09-07T08:29:33 Z ruhanhabib39 Divide and conquer (IZhO14_divide) C++14
0 / 100
 3 ms 7876 KB 
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

const int MAXN = 1e5;

int N;
int X[MAXN + 10], G[MAXN + 10], D[MAXN + 10];
long long gs[MAXN + 10], ds[MAXN + 10];

long long mxt[4 * MAXN + 10];

void init(int cn, int b, int e) {
   if(b == e) {
      mxt[cn] = X[b] - ds[b-1];
      // cerr << "mxt[" << b << "] = " << mxt[cn] << "\n";
      return;
   }
   int m = (b + e) / 2;
   init(2*cn, b, m); init(2*cn+1, m+1, e);
   mxt[cn] = max(mxt[2*cn], mxt[2*cn+1]);
}

int get(int cn, int b, int e, int l, int r, long long mv) {
   if(r < b || l > e) return INF;
   if(mxt[cn] < mv) return INF;
   if(b == e) return b;
   int m = (b + e) / 2;
   int L = get(2*cn, b, m, l, r, mv);
   if(L < INF) return L;
   return get(2*cn+1, m+1, e, l, r, mv);
}

int main() {
   scanf("%d", &N);
   for(int i = 1; i <= N; i++) {
      scanf("%d%d%d", &X[i], &G[i], &D[i]);
   }
   partial_sum(G+1, G+N+1, gs+1);
   partial_sum(D+1, D+N+1, ds+1);
   init(1, 1, N);
   long long res = 0;
   for(int r = 1; r <= N; r++) {
      int l = get(1, 1, N, 1, r, X[r] - ds[r]);
      // cerr << "l = " << l << "\n";
      // cerr << "my[" << r << "] = " << X[r] << " " << ds[r] << "\n";
      long long gold = gs[r] - gs[l-1];
      res = max(res, gold);
   }
   printf("%lld\n", res);
}

Compilation message

divide.cpp: In function 'int main()':
divide.cpp:36:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &N);
                   ^
divide.cpp:38:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d%d%d", &X[i], &G[i], &D[i]);
                                           ^

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 7876 KB Output is correct
2 Correct 0 ms 7876 KB Output is correct
3 Correct 0 ms 7876 KB Output is correct
4 Correct 0 ms 7876 KB Output is correct
5 Correct 0 ms 7876 KB Output is correct
6 Incorrect 0 ms 7876 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 7876 KB Output is correct
2 Correct 0 ms 7876 KB Output is correct
3 Correct 0 ms 7876 KB Output is correct
4 Correct 0 ms 7876 KB Output is correct
5 Incorrect 0 ms 7876 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 7876 KB Output is correct
2 Correct 3 ms 7876 KB Output is correct
3 Runtime error 3 ms 7876 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -