oj.uz

답안 #136598

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
136598 2019-07-25T17:39:16 Z FedericoS 금 캐기 (IZhO14_divide) C++14
100 / 100
 279 ms 12664 KB 
#include <iostream>
#include <set>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pii;

ll N;
ll X[1000006],G[1000006],D[1000006];
ll A[1000006];
ll Gsum[1000006],Dsum[1000006];
ll ans,best;
multiset<pii> S;

ll query(ll x){
	return S.lower_bound({x,-1})->second;
}

int main(){
	cin>>N;
	for(ll i=1;i<N+1;i++){
		cin>>X[i]>>G[i]>>D[i];
		Gsum[i]=Gsum[i-1]+G[i];
		Dsum[i]=Dsum[i-1]+D[i];
	}

	for(ll i=N;i>0;i--){

		S.insert({Dsum[i]-X[i],Gsum[i]});

		bool flag=true;
		auto p=S.find({Dsum[i]-X[i],Gsum[i]});

		p++;
		if(p!=S.end()){
			if(p->second>=Gsum[i]){
				p--;
				S.erase(p);
				flag=false;
			}
		}

		p=S.find({Dsum[i]-X[i],Gsum[i]});
		p--;

		if(flag)
			for(;p!=S.begin();p--){
				auto q=p;
				q--;
				if(q->second>Gsum[i])
					break;
				S.erase(q);
			}

		ans=max(ans,query(Dsum[i-1]-X[i])-Gsum[i-1]);
	}

	cout<<ans;

}

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #2
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 4 ms 376 KB Output is correct
6 Correct 5 ms 504 KB Output is correct
7 Correct 4 ms 376 KB Output is correct
8 Correct 4 ms 376 KB Output is correct
9 Correct 4 ms 476 KB Output is correct
10 Correct 5 ms 504 KB Output is correct
11 Correct 13 ms 1016 KB Output is correct
12 Correct 14 ms 1016 KB Output is correct

Subtask #3
52.0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 596 KB Output is correct
2 Correct 15 ms 888 KB Output is correct
3 Correct 19 ms 892 KB Output is correct
4 Correct 90 ms 2668 KB Output is correct
5 Correct 112 ms 3560 KB Output is correct
6 Correct 229 ms 7288 KB Output is correct
7 Correct 158 ms 6008 KB Output is correct
8 Correct 165 ms 6136 KB Output is correct
9 Correct 155 ms 5920 KB Output is correct
10 Correct 223 ms 9064 KB Output is correct
11 Correct 271 ms 12664 KB Output is correct
12 Correct 279 ms 12584 KB Output is correct