oj.uz

Submission #5064

# Submission time Handle Problem Language Result Execution time Memory
5064 2014-01-30T21:24:16 Z ainta Divide and conquer (IZhO14_divide) C++
100 / 100
 72 ms 4992 KB 
#pragma warning(disable:4996)
#include<stdio.h>
#include<algorithm>
using namespace std;
struct A{
	long long k;
	int num;
	bool operator <(const A &p)const{
		return k != p.k ? k < p.k : num < p.num;
	}
}w[100010], w2[100010];
long long S[100010], tp, res;
int n, i;
int main()
{
	scanf("%d", &n);
	int x, g, d, pv = n;
	for (i = 1; i <= n; i++){
		scanf("%d%d%d", &x, &g, &d);
		S[i] = S[i - 1] + g;
		w2[i].k = tp - x;
		tp = tp + d;
		w[i].k = tp - x;
		w2[i].num = w[i].num = i;
	}
	sort(w + 1, w + n + 1);
	sort(w2 + 1, w2 + n + 1);
	x = 0;
	for (i = n; i >= 1; i--){
		while (pv && w[pv].k >= w2[i].k){
			if (x < w[pv].num)x = w[pv].num;
			pv--;
		}
		if (x >= w2[i].num){
			res = max(res, S[x] - S[w2[i].num - 1]);
		}
	}
	printf("%lld\n", res);
}

Subtask #1
17.0 / 17.0

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

Subtask #2
31.0 / 31.0

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

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 4992 KB Output is correct
2 Correct 4 ms 4992 KB Output is correct
3 Correct 4 ms 4992 KB Output is correct
4 Correct 16 ms 4992 KB Output is correct
5 Correct 20 ms 4992 KB Output is correct
6 Correct 52 ms 4992 KB Output is correct
7 Correct 44 ms 4992 KB Output is correct
8 Correct 32 ms 4992 KB Output is correct
9 Correct 44 ms 4992 KB Output is correct
10 Correct 60 ms 4992 KB Output is correct
11 Correct 72 ms 4992 KB Output is correct
12 Correct 64 ms 4992 KB Output is correct