oj.uz

답안 #338933

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
338933 2020-12-24T09:58:34 Z katearima 금 캐기 (IZhO14_divide) C++14
0 / 100
 1 ms 364 KB 
#include <bits/stdc++.h>
#define ll long long
#define val first
#define ind second
using namespace std;
const int N=1e5+5;
int n,a,b,x;
ll ans;
typedef struct{
	int x, gold , energy;
}camp;
vector<camp> v;
vector<pair<ll, int>> mn;
map <int, ll> g, d;
main(){
	cin>>n;
	for(int i=0; i<n; i++){
		cin>>x>>a>>b;
		v.push_back({x,a,b});
	}
	g[0]=v[0].gold; d[0]=v[0].energy;
	for(int i=1; i<n; i++){
		g[i]=g[i-1]+v[i].gold;
		d[i]=d[i-1]+v[i].energy;
	}
	a=0;
	for(int i=0; i<n; i++){
		b=i; int mid=0;
		
		if(mn.size()==0 || mn[mn.size()-1].val>d[b-1]-v[b].x){
			mn.push_back({d[b-1]-v[b].x,i}); 
		}
		int cost=d[b]-v[b].x;
		int l=0; int r=mn.size()-1;
		while(l<=r){
			mid=(l+r)/2;
			if(mn[mid].val<=cost) r=mid-1;
			else l=mid+1;
		}
		a=mn[mid].ind;
		ans=max(ans, g[b]-g[a-1]);		
	}
	cout<<ans<<endl;
}

Compilation message

divide.cpp:15:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   15 | main(){
      |      ^

Subtask #1
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -