oj.uz

Submission #81001

# Submission time Handle Problem Language Result Execution time Memory
81001 2018-10-23T12:11:20 Z farukkastamonuda Divide and conquer (IZhO14_divide) C++14
100 / 100
 55 ms 9960 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 380 KB Output is correct
3 Correct 2 ms 476 KB Output is correct
4 Correct 2 ms 500 KB Output is correct
5 Correct 2 ms 548 KB Output is correct
6 Correct 2 ms 576 KB Output is correct
7 Correct 2 ms 580 KB Output is correct
8 Correct 2 ms 620 KB Output is correct
9 Correct 2 ms 748 KB Output is correct
10 Correct 2 ms 748 KB Output is correct
11 Correct 2 ms 748 KB Output is correct
12 Correct 2 ms 748 KB Output is correct

Subtask #2
31.0 / 31.0

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

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 896 KB Output is correct
2 Correct 5 ms 1020 KB Output is correct
3 Correct 6 ms 1020 KB Output is correct
4 Correct 21 ms 2940 KB Output is correct
5 Correct 25 ms 2940 KB Output is correct
6 Correct 48 ms 5244 KB Output is correct
7 Correct 38 ms 5340 KB Output is correct
8 Correct 40 ms 5340 KB Output is correct
9 Correct 38 ms 5340 KB Output is correct
10 Correct 39 ms 5340 KB Output is correct
11 Correct 49 ms 7584 KB Output is correct
12 Correct 55 ms 9960 KB Output is correct