제출 #155721

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

divide

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF=1e18;
struct point {
	int x,g,d;
	bool operator<(const point& b)const {
		return x<b.x;
	}
} p[100010];
int n;
ll tree[100010];
ll D[100010],G[100010];
void update(int p,ll x) {
	for(int i=p+1;i>0;i-=i&-i)
		tree[i]=min(tree[i],x);
}
ll query(int p) {
	ll ret=INF;
	for(int i=p+1;i<=100005;i+=i&-i)
		ret=min(ret,tree[i]);
	return ret;
}
int main() {
	scanf("%d",&n);
	fill(tree,tree+100010,INF);
	int i,j,k;
	for(i=1;i<=n;i++) {
		scanf("%d%d%d",&p[i].x,&p[i].g,&p[i].d);
	}
	sort(p+1,p+n+1);
	vector<ll> v;
	for(i=1;i<=n;i++) {
		D[i]=D[i-1]+p[i].d;
		G[i]=G[i-1]+p[i].g;
		v.push_back(p[i].x-D[i-1]);
	}
	sort(all(v));
	v.erase(unique(all(v)),v.end());
	ll res=0;
	for(i=1;i<=n;i++) {
		// x[i]-x[j]<=D[i]-D[j-1]
		// x[i]-D[i]<=x[j]-D[j-1];
		int idx=lower_bound(all(v),p[i].x-D[i])-v.begin();
		ll q=query(idx);
		res=max(res,G[i]-G[i-1]);
		res=max(res,G[i]-q);
		idx=lower_bound(all(v),p[i].x-D[i-1])-v.begin();
		update(idx,G[i-1]);
	}
	printf("%lld",res);
	return 0;
}

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

divide.cpp: In function 'int main()':
divide.cpp:34:8: warning: unused variable 'j' [-Wunused-variable]
  int i,j,k;
        ^
divide.cpp:34:10: warning: unused variable 'k' [-Wunused-variable]
  int i,j,k;
          ^
divide.cpp:32:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
  ~~~~~^~~~~~~~~
divide.cpp:36:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d",&p[i].x,&p[i].g,&p[i].d);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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