Submission #1187962

#	Time	Username	Problem	Language	Result	Execution time	Memory
1187962		AhmadAlhussain	Divide and conquer (IZhO14_divide)	C++20	100 / 100	18 ms	5628 KiB

divide

 #include<iostream>
#include<set>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<vector>
#include<algorithm>
#include<map>
#include<climits>
#include<cmath>
#include<iomanip>
#include<cmath>
#include<numbers>
#include <valarray>
 using namespace std;
#define int long long
int n;
void solve() {
    cin>>n;
    int a[n],g[n],e[n],sum[n+1];
    sum[0]=0;
    int x=0;
    vector<pair<int,int>>v;
    int mx=0;
    for(int i=0;i<n;i++) {
        cin>>a[i]>>g[i]>>e[i];
        sum[i+1]=sum[i]+g[i];

        if(i>0) {
            x-=a[i]-a[i-1];
        }//cout<<x<<' ';
        if(i==0||x<v.back().first) {
            //cout<<x<<' ';
            v.push_back({x,i});
        }

        x+=e[i];
        int l=0,r=v.size()-1,best=v.size()-1;
        while(l<=r) {
            int m=(l+r)/2;
            if(v[m].first<=x) {
                best=v[m].second;
                r=m-1;
            }
            else {
                l=m+1;
            }
        }
        //cout<<best<<'\n';
        mx=max(mx,sum[i+1]-sum[best]);
    }
    cout<<mx;

}
signed main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);
    int t=1;
    while(t--) {
        solve();
    }
}

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