Submission #136596

# Submission time Handle Problem Language Result Execution time Memory
136596 2019-07-25T17:23:39 Z FedericoS Divide and conquer (IZhO14_divide) C++14
48 / 100
1000 ms 4188 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;
set<pii> S;

ll query(ll x){
	ll res=0;
	for(pii p:S)
		if(p.second>=x)
			res=max(res,p.first);
	return res;
}

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({Gsum[i],Dsum[i]-X[i]});
		ans=max(ans,query(Dsum[i-1]-X[i])-Gsum[i-1]);
	}

	cout<<ans;

}
# Verdict Execution time Memory 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 348 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 3 ms 376 KB Output is correct
11 Correct 2 ms 376 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 5 ms 504 KB Output is correct
5 Correct 7 ms 376 KB Output is correct
6 Correct 12 ms 504 KB Output is correct
7 Correct 8 ms 504 KB Output is correct
8 Correct 7 ms 508 KB Output is correct
9 Correct 14 ms 504 KB Output is correct
10 Correct 22 ms 508 KB Output is correct
11 Correct 135 ms 1012 KB Output is correct
12 Correct 138 ms 1016 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 135 ms 1040 KB Output is correct
2 Correct 616 ms 1460 KB Output is correct
3 Correct 618 ms 1504 KB Output is correct
4 Execution timed out 1080 ms 4188 KB Time limit exceeded
5 Halted 0 ms 0 KB -