Submission #1051958

#	Time	Username	Problem	Language	Result	Execution time	Memory
1051958		vjudge1	Divide and conquer (IZhO14_divide)	C++17	0 / 100	0 ms	348 KiB

divide

/*
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░▒░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░▒▒░░▄░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░█░▀░░░░░▌░░░░░░░░░░░░░░▄░░░░░░░░░░░░░░░░░░█░░░░░▌░░░░█░░░░░░░░░░░░░░░░
░░░░░░░░░▌░░░░░░░▐░░░░░░░░▌░░░░██░▀▌░░░░░░░░▐▌░░░░░██░░░░▐░░░░░█░░░░░░░░░░░░░░░░
░░░░░░░░█░░░░░░░░█░░░░░░░█▌░░░░█░░░▌░░░░░░░░█░░░░░█░▐░░░░▐░░░░░▌░░░░░░░░░░░░░░░░
░░░░░░░░█░░░░░░░░█░░░░░░█░▌░░░░█░░░▄░░░░░░░▐▄░███▀░░▐░░░░█░░░░██░░░░░░░░░░░░░░░░
░░░░░░░░░█░░░░░░▐█░░░░░█░▐░░░░▐▌░░░▐░░░░░░█▀░▌░░▀▌░░▐░░░░░█▄░█░░▌░░░░░░░░░░░░░░░
░░░░░░░░░░█▄░░░█░░█░░░█░░█░░░▄█▌░░░░█▄░░▄█░░░█░░░▌░░░█░▄█░░░▀░░░█▄░░░░░░░░░░░░░░
░░░░░░░░░░░░▀▀▀░░░░▀█▀░░░▌▄▄█░█░░░░░░░▀▀░░░░░░██▀░░░░░▀░░░░░░░░░░░▀▀░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░░░░░▄██▀░░░░█░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░▄▄█▀░█░░░░░▐█░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░▌░░░░█░░░░░░▐▌░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░█░░▄█░░░░░░░▐▌░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
░░░░░░░░░░░░░░░░░░▀▀░░░░░░░░░▐▌░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░
*/
// skibidi rizz
#include<bits/stdc++.h>
#define IOS ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie()
#define ll long long
#define ull unsigned long long
#define pb push_back
#define endl "\n"
#define int ll
#define F first     
#define S second
#define db double 
#define ld long double
#define short unsigned short
#define pii pair<int,int>
using namespace std;
const   ll inf = 1e11,MOD=998244353,N=1e5+10,MN=1e9+7,lim=1e6;
const long db Pie=acos(-1);
//...and justice for all
int binpow(int a,int p); 
struct mine{
  int x,g,d;
};
mine a[N];
int n;
int ans=0;
void rec(int l,int r){
  if(l==r){
    ans=max(ans,a[l].g);
    return ;
  }
  int m=(l+r)/2;
    rec(l,m);
    rec(m+1,r);
  int curg=0,cure=0;
  vector<pair<int,int>>v;
  int last=0;
  for(int i=m+1;i<=r;i++){
    v.pb({a[i].d-(a[i].x-a[m+1].x),a[i].g+last});
    last+=a[i].g;
  }
  sort(v.begin(),v.end());
  // for(int i=0;i<v.size();i++){
  //   cout<<v[i].F<<' ';
  // }
  // cout<<endl;
  vector<int>suf(v.size()+1,-inf);
  for(int i=v.size()-1;i>=0;i--){
    suf[i]=max(suf[i+1],v[i].S);
  }
  for(int i=m;i>=l;i--){
    cure+=a[i].d-(a[i+1].x-a[i].x);
    // cout<<cure<<" ";
    curg+=a[i].g;
    int lx=0,rx=v.size()-1;
    int res=-1;
    while(lx<=rx){
      int mid=(lx+rx)/2;
      if(-cure<=v[mid].F){
        rx=mid-1;
        res=mid;
      }
      else{
        lx=mid+1;
      }
    }
    // cout<<endl<<res;
    if(res!=-1){
      ans=max(ans,suf[res]+curg);
    }
  }
}
const void solve(){
  cin>>n;
  for(int i=0;i<n;i++){
    cin>>a[i].x>>a[i].g>>a[i].d;
  }
  rec(0,n-1);
  cout<<ans<<endl;
}
main() {
    srand(time(NULL));
    IOS;
    //freopen("c  oins.in", "r", stdin);
    //freopen("coins.out", "w", stdout);
    int UwU=1;
    // cin>>UwU;      
    for(int i=1;i<=UwU;i++) { 
      // cout<<"Case "<<i<<": ";
        solve(); 
      // cout<<endl;
    }
    cout<<fixed<<setprecision(10);
    cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n"; 
}
// int binmul(int a,int b){}
int binpow(int a,int p){if(p==0)return 1;if(p%2){return ((binpow(a,p-1)*a)%MOD);}int res=binpow(a,p/2)%MOD; return (res*res)%MOD;}

Compilation message (stderr)

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

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