oj.uz

Submission #240450

# Submission time Handle Problem Language Result Execution time Memory
240450 2020-06-19T16:37:41 Z DS007 Divide and conquer (IZhO14_divide) C++14
0 / 100
 5 ms 384 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
 
const int N = 4;
int x[N], g[N], d[N], pg[N], pd[N], t[N * 4], n;
 
int build(int v, int l, int r) {
	if (l == r)
		return t[v] = pd[l] - x[l];
 
	int mid = (l + r) / 2;
	return t[v] = max(build(v * 2, l, mid), build(v * 2 + 1, mid + 1, r));
}
 
int query(int v, int l, int r, int tl, int tr) {
	if (tl > tr)
		return -1e18;
	else if (l == tl && r == tr)
		return t[v];
 
	int mid = (l + r) / 2;
	return max(query(v * 2, l, mid, tl, min(mid, tr)), query(v * 2 + 1, mid + 1, r, max(mid + 1, tl), tr));
}
 
int solve(int l, int r, int val) {
	if (query(1, 0, n - 1, l, r) < val)
		return -1;
	else if (l == r)
		return l;
 
	int mid = (l + r) / 2;
	if (query(1, 0, n - 1, mid + 1, r) >= val)
		return solve(mid + 1, r, val);
	else
		return solve(l, mid, val);
}
 
int solveTestCase() {
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> x[i] >> g[i] >> d[i];
 
	pg[0] = g[0], pd[0] = d[0];
	for (int i = 1; i < n; i++)
		pg[i]  = pg[i - 1] + g[i], pd[i] = pd[i - 1] + d[i];
 
	build(1, 0, n - 1);
	int ans = *max_element(g, g + n);
	//cout << pd[3] - x[3] << "\n";
	//for (int i = 0; i < n; i++)
	//    cout << query(1, 0, n - 1, i, i) << "\n";
 
	for (int i = n - 2; i >= 0; i--) {
		int j = solve(i + 1, n - 1, pd[i] - d[i] - x[i]);
		//cout << j << "\n";
		if (j != -1)
			ans = max(ans, pg[j] - pg[i] + g[i]);
	}
 
	cout << ans;
}
 
signed main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
 
	int t = 1;
	//cin >> t;
	while (t--)
		solveTestCase();
	return 0;
}

Compilation message

divide.cpp: In function 'long long int solveTestCase()':
divide.cpp:62:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 4 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 4 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Incorrect 4 ms 384 KB Output isn't correct
3 Halted 0 ms 0 KB -