oj.uz

답안 #49534

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
49534 2018-05-31T00:07:29 Z tmwilliamlin168 금 캐기 (IZhO14_divide) C++14
100 / 100
 85 ms 4144 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long

inline int in() {
	int result = 0;
	char ch = getchar_unlocked();
	while (true) {
		if(ch >= '0' && ch <= '9')
			break;
		ch = getchar_unlocked();
	}
	result = ch-'0';
	while(true) {
		ch = getchar_unlocked();
		if (ch < '0' || ch > '9')
			break;
		result = result*10 + (ch - '0');
	}
	return result;
}
inline void out(ll x) {
	ll rev=x;
	int count = 0;
	while((rev % 10) == 0) {
++count;
rev /= 10;
} //obtain the count of the number of 0s
	rev = 0;
	while(x != 0) {
rev = rev*10 + x % 10;
x /= 10;
} //store reverse of N in rev
	while(rev != 0) {
putchar_unlocked(rev % 10 + '0');
rev /= 10;
}
	while(count--)
putchar_unlocked('0');
}

const int mxN=1e5;
int n, x[mxN];
ll pg[mxN+1], pd[mxN+1], pts[mxN], ft[mxN+1], ans;

inline void upd(int i, ll x) {
	for(++i; i<=n; i+=i&-i)
		ft[i]=max(x, ft[i]);
}

inline ll qry(int i) {
	ll r=0;
	for(; i; i-=i&-i)
		r=max(ft[i], r);
	return r;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	for(int i=0; i<n; ++i) {
		cin >> x[i] >> pg[i+1] >> pd[i+1], pg[i+1]+=pg[i], pd[i+1]+=pd[i];
		pts[i]=x[i]-pd[i+1];
	}
	sort(pts, pts+n);
	for(int i=n-1; i>=0; --i) {
		upd(lower_bound(pts, pts+n, x[i]-pd[i+1])-pts, pg[i+1]);
		ans=max(qry(upper_bound(pts, pts+n, x[i]-pd[i])-pts)-pg[i], ans);
	}
	cout << ans;
}

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 408 KB Output is correct
4 Correct 2 ms 484 KB Output is correct
5 Correct 2 ms 560 KB Output is correct
6 Correct 2 ms 560 KB Output is correct
7 Correct 2 ms 560 KB Output is correct
8 Correct 2 ms 608 KB Output is correct
9 Correct 3 ms 696 KB Output is correct
10 Correct 2 ms 696 KB Output is correct
11 Correct 2 ms 696 KB Output is correct
12 Correct 2 ms 696 KB Output is correct

Subtask #2
31.0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 696 KB Output is correct
2 Correct 2 ms 696 KB Output is correct
3 Correct 2 ms 696 KB Output is correct
4 Correct 2 ms 696 KB Output is correct
5 Correct 3 ms 696 KB Output is correct
6 Correct 2 ms 696 KB Output is correct
7 Correct 3 ms 696 KB Output is correct
8 Correct 2 ms 696 KB Output is correct
9 Correct 4 ms 696 KB Output is correct
10 Correct 4 ms 696 KB Output is correct
11 Correct 5 ms 748 KB Output is correct
12 Correct 6 ms 748 KB Output is correct

Subtask #3
52.0 / 52.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 748 KB Output is correct
2 Correct 7 ms 880 KB Output is correct
3 Correct 7 ms 880 KB Output is correct
4 Correct 31 ms 2412 KB Output is correct
5 Correct 33 ms 2412 KB Output is correct
6 Correct 63 ms 4092 KB Output is correct
7 Correct 55 ms 4092 KB Output is correct
8 Correct 55 ms 4092 KB Output is correct
9 Correct 52 ms 4092 KB Output is correct
10 Correct 57 ms 4140 KB Output is correct
11 Correct 69 ms 4140 KB Output is correct
12 Correct 85 ms 4144 KB Output is correct