Submission #1189570

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189570		diyah999	Divide and conquer (IZhO14_divide)	C++20	17 / 100	0 ms	528 KiB

divide

#include<bits/stdc++.h>
using namespace std;
#define w long long


signed main(){
  ios_base::sync_with_stdio(0);cin.tie(0);
  
  w n;
  cin>>n;
  
  vector<w>x(n),g(n),d(n);
  
  for(w i=0;i<n;++i)
    cin>>x[i]>>g[i]>>d[i];
  
  
  
  w j=-1,ans=0,totale=0,totalg=0;
  
  for(w i=0;i<n;++i){
    if(i!=0){
      
      totale-=d[i-1];
      totalg-=g[i-1];
      
    }
    
    while(j+1<n && totale+d[j+1]>=x[j+1]-x[i]){
      j++;
      totalg+=g[j];
      totale+=d[j];
    }
    
    // cout<<i<<' '<<j<<' '<<totale<<endl;
    ans=max(ans,totalg);
  }
  
  cout<<ans;
  
  
}

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