답안 #98345

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
98345 2019-02-22T17:25:26 Z luciocf 금 캐기 (IZhO14_divide) C++14
100 / 100
162 ms 8184 KB
#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;
const int inf = 1e9+10;

typedef long long ll;

int x[maxn], g[maxn], d[maxn];

ll s[maxn], p[maxn];

ll tree[4*maxn];

void build(int node, int l, int r)
{
	if (l == r)
	{
		tree[node] = s[l-1]-x[l];
		return;
	}

	int mid = (l+r)>>1;

	build(2*node, l, mid); build(2*node+1, mid+1, r);

	tree[node] = min(tree[2*node], tree[2*node+1]);
}

int query(int node, int l, int r, ll v)
{
	if (l == r)
	{
		if (tree[node] <= v) return l;
		return inf;
	}

	int mid = (l+r)>>1;

	if (tree[2*node] <= v) return query(2*node, l, mid, v);
	return query(2*node+1, mid+1, r, v);
}

int main(void)
{
	int n;
	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		cin >> x[i] >> g[i] >> d[i];

		s[i] = s[i-1]+(ll)d[i];
		p[i] = p[i-1]+(ll)g[i];
	}

	build(1, 1, n);

	ll ans = 0LL;

	for (int i = 1; i <= n; i++)
	{
		int pos = query(1, 1, n, s[i]-(ll)x[i]);

		if (pos != inf && pos <= i) ans = max(ans, p[i]-p[pos-1]);
	}

	cout << ans << "\n";
}
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 2 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 4 ms 384 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 420 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 428 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 4 ms 392 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 12 ms 768 KB Output is correct
12 Correct 13 ms 768 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 612 KB Output is correct
2 Correct 10 ms 1024 KB Output is correct
3 Correct 14 ms 1108 KB Output is correct
4 Correct 71 ms 3812 KB Output is correct
5 Correct 78 ms 4348 KB Output is correct
6 Correct 162 ms 8184 KB Output is correct
7 Correct 120 ms 6908 KB Output is correct
8 Correct 149 ms 7064 KB Output is correct
9 Correct 139 ms 6876 KB Output is correct
10 Correct 133 ms 6856 KB Output is correct
11 Correct 149 ms 7544 KB Output is correct
12 Correct 150 ms 7548 KB Output is correct