oj.uz

Submission #68591

# Submission time Handle Problem Language Result Execution time Memory
68591 2018-08-17T12:48:44 Z cdemirer Divide and conquer (IZhO14_divide) C++17
100 / 100
 62 ms 17796 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef pair<double, double> dodo;
typedef pair<ll, ll> llp;
typedef vector<llp> vllp;
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define INFll 1000000000000000000ll

int N;
ll X[100000], G[100000], D[100000];
ll preG[100000], preD[100000];
ll A[100000];

int f(ll lim) {
	int l = 0, r = N;
	while (l < r) {
		int mid = (l+r)/2;
		if (A[mid] <= lim) r = mid;
		else l = mid+1;
	}
	return r;
}

int main(int argc, char **argv) {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> N;
	for (int i = 0; i < N; i++) cin >> X[i] >> G[i] >> D[i];
	for (int i = 0; i < N; i++) preG[i] = G[i] + (i?preG[i-1]:0);
	for (int i = 0; i < N; i++) preD[i] = D[i] + (i?preD[i-1]:0);
	for (int i = 0; i < N; i++) A[i] = -X[i] + (i?preD[i-1]:0);
	for (int i = 0; i < N; i++) A[i] = min(A[i], (i?A[i-1]:INFll));
	ll ans = G[0];
	for (int i = 0; i < N; i++) {
		int l = f(preD[i]-X[i]);
		ans = max(ans, preG[i]-(l?preG[l-1]:0));
	}
	cout << ans << endl;

	return 0;
}

Subtask #1
17.0 / 17.0

# 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 416 KB Output is correct
4 Correct 3 ms 548 KB Output is correct
5 Correct 3 ms 548 KB Output is correct
6 Correct 2 ms 548 KB Output is correct
7 Correct 2 ms 548 KB Output is correct
8 Correct 2 ms 548 KB Output is correct
9 Correct 2 ms 548 KB Output is correct
10 Correct 2 ms 548 KB Output is correct
11 Correct 2 ms 548 KB Output is correct
12 Correct 2 ms 628 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 628 KB Output is correct
2 Correct 2 ms 628 KB Output is correct
3 Correct 2 ms 728 KB Output is correct
4 Correct 2 ms 728 KB Output is correct
5 Correct 2 ms 728 KB Output is correct
6 Correct 3 ms 860 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 2 ms 940 KB Output is correct
10 Correct 3 ms 964 KB Output is correct
11 Correct 5 ms 1132 KB Output is correct
12 Correct 5 ms 1368 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1368 KB Output is correct
2 Correct 6 ms 1812 KB Output is correct
3 Correct 6 ms 1812 KB Output is correct
4 Correct 21 ms 3612 KB Output is correct
5 Correct 25 ms 3704 KB Output is correct
6 Correct 49 ms 5916 KB Output is correct
7 Correct 39 ms 7836 KB Output is correct
8 Correct 41 ms 9792 KB Output is correct
9 Correct 62 ms 11460 KB Output is correct
10 Correct 41 ms 13188 KB Output is correct
11 Correct 46 ms 15432 KB Output is correct
12 Correct 49 ms 17796 KB Output is correct