oj.uz

Submission #525365

# Submission time Handle Problem Language Result Execution time Memory
525365 2022-02-11T13:33:36 Z Dilshod_Imomov Divide and conquer (IZhO14_divide) C++17
0 / 100
 0 ms 204 KB 
# include <bits/stdc++.h>
# define speed ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0)
// # define int long long
# define fi first
# define se second

using namespace std;

const int N = 1e5 + 7;
const int mod = 1e9 + 7;
// const int INF = 1e18;

int x[N], g[N], d[N];

int32_t main() {
   speed;
   int n;
   cin >> n;
   for ( int i = 1; i <= n; i++ ) {
      cin >> x[i] >> g[i] >> d[i];
      d[i] += d[i - 1];
   }
   int mx = 0, sum = 0, l = 1, r = 0;
   for ( int i = 1; i <= n; i++ ) {
      if ( l > r ) {
         l = i;
         r = i;
         sum = g[i];
      }
      else {
         while ( l < r && x[i] - x[l] > d[i] - d[l - 1] ) {
            sum -= g[l];
            l++;
         }
         if ( x[i] - x[l] <= d[i] - d[l - 1] ) {
            r = i;
            sum += g[i];
         }
      }
      mx = max( mx, sum );
   }
   cout << mx;
}

Subtask #1
0 / 17.0

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

Subtask #2
0 / 31.0

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

Subtask #3
0 / 52.0

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