Submission #1158879

#	Time	Username	Problem	Language	Result	Execution time	Memory
1158879		the_ZHER	Divide and conquer (IZhO14_divide)	C++20	100 / 100	47 ms	6444 KiB

divide

#include <bits/stdc++.h>
#define boost ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define int long long
using namespace std;
const int inf=1e17;
const int N=1e5+5;
const int N1=1e5+5;
const int N2=5e6+6;
const int mod=1e9+7;
const int k1=447;
struct edge{
    int d,in;
};
struct edge1{
    int x,g,d;
};
vector<edge1>v;
int dp[N];
int dp1[N];
int dp2[N];
int divide(int l,int r){
    if(r-l+1==1){
        return v[r].g;
    }
    int mid=(l+r)/2;
    int ans=divide(l,mid);
    int ans1=divide(mid+1,r);
    vector<pair<int,int> >v2;
    int sum=0;
    int cnt=0;
    for(int i=mid;i>=l;i--){
        cnt=dp1[i-1];
        sum+=v[i].g;
        v2.push_back({-cnt+v[i].x,sum});
    }
    sort(v2.begin(),v2.end());
    for(int i=v2.size()-1;i>=0;i--){
        dp2[i]=v2[i].second;
        dp2[i]=max(dp2[i],dp2[i+1]);
    }
    int ans2=0;
    sum=0;
    for(int i=mid+1;i<=r;i++){
        int l1=0,r1=v2.size()-1;
        int cnt=v[i].x-dp1[i];
        sum+=v[i].g;
        while(l1+1<r1){
            int mid1=(l1+r1)/2;
            if(cnt>v2[mid1].first){
                l1=mid1;
            }else{
                r1=mid1;
            }
        }
        if(cnt<=v2[l1].first){
            r1=l1;
        }
        if(cnt<=v2[r1].first){
            ans2=max(ans2,sum+dp2[r1]);
        }
    }
    for(int i=0;i<=v2.size();i++){
        dp2[i]=0;
    }
    v2.clear();
    return max({ans,ans1,ans2});
}
signed main(){
boost;
    int n;
    cin>>n;
    v.push_back({0,0,0});
    for(int i=1;i<=n;i++){
        edge1 x;
        cin>>x.x>>x.g>>x.d;
        dp[i]=dp[i-1]+x.g;
        dp1[i]=dp1[i-1]+x.d;
        v.push_back(x);
    }
    int ans=divide(1,n);
    cout<<ans;
}  

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