제출 #240450

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
240450		DS007	Divide and conquer (IZhO14_divide)	C++14	0 / 100	5 ms	384 KiB

divide

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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
• Subtask 2: 0 / 31
• Subtask 3: 0 / 52