oj.uz

Submission #5395

# Submission time Handle Problem Language Result Execution time Memory
5395 2014-04-29T11:07:56 Z gs12117 Divide and conquer (IZhO14_divide) C++
0 / 100
 0 ms 6948 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;
	freopen("divide.in","r",stdin);
	freopen("divide.out","w",stdout);
	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
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 6948 KB open (syscall #2) was called by the program (disallowed syscall)
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 6948 KB open (syscall #2) was called by the program (disallowed syscall)
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 52.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 6948 KB open (syscall #2) was called by the program (disallowed syscall)
2 Halted 0 ms 0 KB -