oj.uz

Submission #5396

# Submission time Handle Problem Language Result Execution time Memory
5396 2014-04-29T11:08:14 Z gs12117 Divide and conquer (IZhO14_divide) C++
100 / 100
 68 ms 6952 KB 
#include<stdio.h>
#include<algorithm>
int n;
int x[100100];
int gold[100100];
long long int gsum[100100];
int eng[100100];
long long int esum[100100];
struct data{
	long long int gtot;
	long long int etot;
	bool operator<(const data &r)const{
		return etot<r.etot||(etot==r.etot&&gtot<r.gtot);
	}
};
data points[200100];
long long int ans;
int main(){
	int i;
	long long int ming;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		scanf("%d%d%d",&x[i],&gold[i],&eng[i]);
		gsum[i+1]=gold[i]+gsum[i];
		esum[i+1]=eng[i]+esum[i];
	}
	for(i=0;i<n;i++){
		points[i*2].gtot=gsum[i];
		points[i*2].etot=esum[i]-x[i];
		points[i*2+1].gtot=gsum[i+1];
		points[i*2+1].etot=esum[i+1]-x[i];
	}
	std::sort(points,points+2*n);
	ming=points[0].gtot;
	for(i=1;i<2*n;i++){
		if(ming>points[i].gtot)ming=points[i].gtot;
		if(ans<points[i].gtot-ming)ans=points[i].gtot-ming;
	}
	printf("%lld",ans);
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6952 KB Output is correct
2 Correct 0 ms 6952 KB Output is correct
3 Correct 0 ms 6952 KB Output is correct
4 Correct 0 ms 6952 KB Output is correct
5 Correct 0 ms 6952 KB Output is correct
6 Correct 0 ms 6952 KB Output is correct
7 Correct 0 ms 6952 KB Output is correct
8 Correct 0 ms 6952 KB Output is correct
9 Correct 0 ms 6952 KB Output is correct
10 Correct 0 ms 6952 KB Output is correct
11 Correct 0 ms 6952 KB Output is correct
12 Correct 0 ms 6952 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6952 KB Output is correct
2 Correct 0 ms 6952 KB Output is correct
3 Correct 0 ms 6952 KB Output is correct
4 Correct 0 ms 6952 KB Output is correct
5 Correct 0 ms 6952 KB Output is correct
6 Correct 0 ms 6952 KB Output is correct
7 Correct 0 ms 6952 KB Output is correct
8 Correct 0 ms 6952 KB Output is correct
9 Correct 0 ms 6952 KB Output is correct
10 Correct 0 ms 6952 KB Output is correct
11 Correct 4 ms 6952 KB Output is correct
12 Correct 4 ms 6952 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6952 KB Output is correct
2 Correct 4 ms 6952 KB Output is correct
3 Correct 4 ms 6952 KB Output is correct
4 Correct 24 ms 6952 KB Output is correct
5 Correct 24 ms 6952 KB Output is correct
6 Correct 60 ms 6952 KB Output is correct
7 Correct 40 ms 6952 KB Output is correct
8 Correct 40 ms 6952 KB Output is correct
9 Correct 48 ms 6952 KB Output is correct
10 Correct 64 ms 6952 KB Output is correct
11 Correct 68 ms 6952 KB Output is correct
12 Correct 64 ms 6952 KB Output is correct