Submission #1034913

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034913		pera	Divide and conquer (IZhO14_divide)	C++17	0 / 100	2 ms	2652 KiB

divide

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 1e5 + 1;
int n , ans = 0;
vector<int> x(N) , g(N) , d(N);
void solve(int l , int r){
   if(l > r){
      return;
   }
   int m = (l + r) / 2 , sum_R = 0 , sum_G = 0;
   map<int , int> M;
   for(int R = m + 1;R <= r;R ++){
      sum_R += d[R];
      sum_G += g[R];
      M[(x[R] - x[m]) - sum_R] = sum_G;
   }
   //sl + sr = x[R] - x[L] = (x[m] - x[L]) + (x[R] - x[m])
   //sl - (x[m] - x[L]) = (x[R] - x[m]) - sr
   int sum_L = 0;
   sum_G = 0;
   for(int L = m;L >= l;L --){
      sum_L += d[L];
      sum_G += g[L];
      if(M.find(sum_L - (x[m] - x[L])) != M.end()){
         ans = max(ans , sum_G + M[sum_L - (x[m] - x[L])]);
      }
   }
   if(d[m] == 1){
      ans = max(ans , g[m]);
   }
   solve(l  , m - 1);
   solve(m + 1 , r);
}
main(){
   cin >> n;
   for(int i = 1;i <= n;i ++){
      cin >> x[i] >> g[i] >> d[i];
   }
   solve(1 , n);
   cout << ans << endl;
}

Compilation message (stderr)

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

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