제출 #68440

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

divide

#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long
#define ii pair<int,int>
#define iii pair<int,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)>>1)
#define all(x) x.begin(),x.end()
#define dbgs(x) cerr<<(#x)<<" --> "<<(x)<<" "
#define dbg(x) cerr<<(#x)<<" --> "<<(x)<<endl;getchar()
#define pw(x) (1<<(x))
#define inf 10000000000000000
#define MOD 1000000007
#define N 200005
#define MAX 10000006
#define LOG 30
#define KOK 200
using namespace std;

ll S[N*4],preE[N],preG[N],ans;
int n,x,g,d,coord[N],tut[2][N];
vector< pair<ll, ii > > v;

void up(int node,int bas,int son,int x,ll val) {

	if(bas>x || son<x) return ;

	if(bas==x && son==x) {

		umax(S[node],val);

		return ;

	}

	up(node*2,bas,orta,x,val);
	up(node*2+1,orta+1,son,x,val);

	S[node]=max(S[node*2],S[node*2+1]);

}

ll get(int node,int bas,int son,int x,int y) {

	if(bas>y || son<x) return -inf;

	if(bas>=x && son<=y) return S[node];

	return max(get(node*2,bas,orta,x,y),get(node*2+1,orta+1,son,x,y)); 

}

int main() {

//	freopen("input.txt","r",stdin);

	scanf("%d",&n);

	for(int i=1;i<=n;i++) {

		scanf("%d %d %d",&x,&g,&d);

		preE[i]=preE[i-1]+d;
		preG[i]=preG[i-1]+g;

		coord[i]=x;

	}	

	for(int i=1;i<=n;i++) {

		v.pb({preE[i]-coord[i],{i,1}});
		v.pb({preE[i-1]-coord[i],{i,0}});

	}

	sort(all(v));

	int cnt=0;

	for(int i=0;i<sz(v);i++) {

		++cnt;

		tut[v[i].nd.nd][v[i].nd.st]=cnt;

		while(i+1<sz(v) && v[i+1].st==v[i].st) {

			i++;
			tut[v[i].nd.nd][v[i].nd.st]=cnt;

		}

	}

	for(int i=0;i<N*4;i++) S[i]=-inf;

	for(int i=1;i<=n;i++) {

		up(1,1,cnt,tut[0][i],-preG[i-1]);

		umax(ans,get(1,1,cnt,1,tut[1][i])+preG[i]);

	}

	printf("%lld\n",ans);

}

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

divide.cpp: In function 'int main()':
divide.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
divide.cpp:66:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d",&x,&g,&d);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~

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