oj.uz

Submission #136583

# Submission time Handle Problem Language Result Execution time Memory
136583 2019-07-25T15:56:42 Z FedericoS Divide and conquer (IZhO14_divide) C++14
0 / 100
 502 ms 1324 KB 
#include <iostream>
#include <set>
using namespace std;
typedef pair<int,int> pii;

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

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

int main(){
	cin>>N;
	for(int 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(int 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;

}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 372 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Incorrect 2 ms 376 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 364 KB Output is correct
3 Correct 4 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Incorrect 7 ms 504 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 880 KB Output is correct
2 Correct 487 ms 1144 KB Output is correct
3 Incorrect 502 ms 1324 KB Output isn't correct
4 Halted 0 ms 0 KB -