답안 #49535

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
49535 2018-05-31T00:08:20 Z tmwilliamlin168 금 캐기 (IZhO14_divide) C++14
100 / 100
38 ms 4096 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() {
	n=in();
	for(int i=0; i<n; ++i) {
		x[i]=in(), pg[i+1]=in()+pg[i], pd[i+1]=in()+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);
	}
	out(ans);
}
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 416 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 11 ms 492 KB Output is correct
6 Correct 2 ms 544 KB Output is correct
7 Correct 2 ms 672 KB Output is correct
8 Correct 2 ms 672 KB Output is correct
9 Correct 2 ms 672 KB Output is correct
10 Correct 2 ms 672 KB Output is correct
11 Correct 2 ms 672 KB Output is correct
12 Correct 3 ms 744 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 744 KB Output is correct
2 Correct 3 ms 760 KB Output is correct
3 Correct 3 ms 760 KB Output is correct
4 Correct 3 ms 760 KB Output is correct
5 Correct 3 ms 760 KB Output is correct
6 Correct 2 ms 760 KB Output is correct
7 Correct 2 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 2 ms 760 KB Output is correct
11 Correct 3 ms 764 KB Output is correct
12 Correct 4 ms 768 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 768 KB Output is correct
2 Correct 4 ms 896 KB Output is correct
3 Correct 4 ms 896 KB Output is correct
4 Correct 15 ms 2300 KB Output is correct
5 Correct 16 ms 2356 KB Output is correct
6 Correct 31 ms 4092 KB Output is correct
7 Correct 27 ms 4092 KB Output is correct
8 Correct 28 ms 4096 KB Output is correct
9 Correct 29 ms 4096 KB Output is correct
10 Correct 30 ms 4096 KB Output is correct
11 Correct 38 ms 4096 KB Output is correct
12 Correct 33 ms 4096 KB Output is correct