제출 #403322

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
403322		fadi57	금 캐기 (IZhO14_divide)	C++14	100 / 100	184 ms	7908 KiB

divide

#include<bits/stdc++.h>
using namespace std;
const int mx=1e5+5;
typedef long long ll;
int inf=1e9+10;
const int mod=1e9+7;
int d[mx];
int g[mx];
int x[mx];
ll pref[mx];
ll pref2[mx];
int n,m;
ll sum=0;
ll seg[4*mx];
void build(int node,int st,int en){

 if(st==en){
    seg[node]=pref[st];

     return ;
 }
 int mid=(st+en)/2;

   build(node*2,st,mid); build(node*2+1,mid+1,en);
   seg[node]=max(seg[node*2],seg[node*2+1]);

 }
 void update(int node,int st,int en,int idx){


if(st>idx||en<idx){return;}
 if(st==en){
    seg[node]=-1e17;
    return ;
 }

 int mid=(st+en)/2;
 update(node*2,st,mid,idx);
 update(node*2+1,mid+1,en,idx);
 seg[node]=max(seg[node*2],seg[node*2+1]);
   return ;
 }
 int query(int node,int st,int en){

 if(st==en){
    return st;
 }

 int mid=(st+en)/2;
 if((seg[node*2+1]+sum)>=0){
        return query(node*2+1,mid+1,en);

 }else{

   return query(node*2,st,mid);
   }


 }


int main(){
cin>>n;
ll ans=0;
for(int i=1;i<=n;i++){
    cin>>x[i]>>g[i]>>d[i];
    pref[i]=pref[i-1]+d[i];

  pref2[i]=g[i]+pref2[i-1];

}
for(int i=1;i<=n;i++){
    pref[i]=pref[i-1]+d[i];
    if(i>1){


    pref[i]-=(x[i]-x[i-1]);
    }
     //cout<<pref[i]<<" ";
}
//cout<<endl;

 ll sum2=0;
 int j=0;
 build(1,1,n);
 x[0]=x[1];
for(int i=1;i<=n;i++){
      sum+=(x[i]-x[i-1])-d[i-1];
      int l=query(1,1,n);
      ans=max(pref2[l]-pref2[i-1],ans);
//cout<<l;
update(1,1,n,i);
}
cout<<ans;
 }

컴파일 시 표준 에러 (stderr) 메시지

divide.cpp: In function 'int main()':
divide.cpp:83:5: warning: unused variable 'sum2' [-Wunused-variable]
   83 |  ll sum2=0;
      |     ^~~~
divide.cpp:84:6: warning: unused variable 'j' [-Wunused-variable]
   84 |  int j=0;
      |      ^

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