oj.uz

Submission #31761

# Submission time Handle Problem Language Result Execution time Memory
31761 2017-09-07T08:30:38 Z ruhanhabib39 Divide and conquer (IZhO14_divide) C++14
100 / 100
 73 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]);
   }
   for(int i = 1; i <= N; i++) {
      gs[i] = G[i] + gs[i-1];
      ds[i] = D[i] + ds[i-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
17.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 Correct 0 ms 7876 KB Output is correct
7 Correct 0 ms 7876 KB Output is correct
8 Correct 0 ms 7876 KB Output is correct
9 Correct 0 ms 7876 KB Output is correct
10 Correct 0 ms 7876 KB Output is correct
11 Correct 0 ms 7876 KB Output is correct
12 Correct 0 ms 7876 KB Output is correct

Subtask #2
31.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 Correct 0 ms 7876 KB Output is correct
6 Correct 0 ms 7876 KB Output is correct
7 Correct 0 ms 7876 KB Output is correct
8 Correct 0 ms 7876 KB Output is correct
9 Correct 0 ms 7876 KB Output is correct
10 Correct 0 ms 7876 KB Output is correct
11 Correct 3 ms 7876 KB Output is correct
12 Correct 3 ms 7876 KB Output is correct

Subtask #3
52.0 / 52.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 3 ms 7876 KB Output is correct
4 Correct 23 ms 7876 KB Output is correct
5 Correct 29 ms 7876 KB Output is correct
6 Correct 59 ms 7876 KB Output is correct
7 Correct 36 ms 7876 KB Output is correct
8 Correct 49 ms 7876 KB Output is correct
9 Correct 49 ms 7876 KB Output is correct
10 Correct 53 ms 7876 KB Output is correct
11 Correct 49 ms 7876 KB Output is correct
12 Correct 73 ms 7876 KB Output is correct