Submission #765629

#	Time	Username	Problem	Language	Result	Execution time	Memory
765629		LeaRouse	Divide and conquer (IZhO14_divide)	C++14	100 / 100	27 ms	9744 KiB

divide

#include<bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0);
#define ll long long
#define ff first
#define ss second
using namespace std;
const int MAX = 2e5+5;
const ll INF=1e18;
ll O[MAX],E[MAX],A[MAX],B[MAX],C[MAX],P[MAX];
pair<int,int>dp[(1<<21)+5];
vector<int>v[MAX];
int bi(int x){
    int ini=1;
    int fin=x;
    while(ini<fin){
        int mid=(ini+fin-1)/2;
        if(P[mid]>E[x]-A[x]){
            ini=mid+1;
        }
        else{
            fin=mid;
        }
    }
    return ini;
}

void go(){
    int n;  cin>>n;
    E[0]=0; O[0]=0; P[0]=INF;
    for(int i=1;i<=n;i++){
        cin>>A[i]>>B[i]>>C[i];
        O[i]=O[i-1]+B[i];//oro acumulado 
        E[i]=E[i-1]+C[i];//energia acumulada
        P[i]=min(P[i-1],E[i-1]-A[i]);//dif energia - pos
    }
    ll ans=0;
    for(int i=1;i<=n;i++){
        int a=bi(i);//buscamos el indice j <i / jes el minimo y cumpla la barrera
        //cout<<a<<endl;
        if(P[a]<=E[i]-A[i]){
            ans=max(ans,O[i]-O[a-1]);
        }
    }
    cout<<ans<<endl;
}
 
int main(){
    fastio;
    go();
    return 0;
}

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