Submission #1035934

#	Time	Username	Problem	Language	Result	Execution time	Memory
1035934		pera	Divide and conquer (IZhO14_divide)	C++17	100 / 100	130 ms	7736 KiB

divide

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 100;
int n , ans = 0 , SZ;
vector<int> x(N) , g(N) , e(N) , sum_e(N) , sum_g(N);
void solve(int l , int r){
   if(l > r){
      return;
   }
   int m = (l + r) / 2;
   for(int i = l;i <= r;i ++){
      sum_e[i] = sum_e[i - 1] + e[i];
      sum_g[i] = sum_g[i - 1] + g[i];
   }
   vector<pair<int , int>> u;
   for(int i = l;i <= r;i ++){
      if(i < m){
         u.push_back({sum_e[i - 1] - x[i] , i});
      }else{
         u.push_back({sum_e[i] - x[i] , i});
      }
   }
   sort(u.begin() , u.end());
   int mn = 1e15;
   for(auto [_value , id] : u){
      if(id < m){
         mn = min(mn , sum_g[id - 1]);
      }else{
         ans = max(ans , sum_g[id] - mn);
         if(sum_e[id] - sum_e[m - 1] >= x[id] - x[m]){
            ans = max(ans , sum_g[id] - sum_g[m - 1]);
         }
      }
   }
   for(int i = l;i <= r;i ++){
      sum_e[i] = sum_g[i] = 0;
   }
   solve(l , m - 1);
   solve(m + 1 , r);
}
main(){
   cin >> n;
   for(int i = 1;i <= n;i ++){
      cin >> x[i] >> g[i] >> e[i];
   }
   x[n + 1] = 1e15;
   x[0] = -1e15;
   solve(1 , n);
   cout << ans << endl;
}

Compilation message (stderr)

divide.cpp:42:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   42 | main(){
      | ^~~~

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52