oj.uz

Submission #68435

# Submission time Handle Problem Language Result Execution time Memory
68435 2018-08-17T07:00:57 Z tatatan Divide and conquer (IZhO14_divide) C++11
100 / 100
 55 ms 3712 KB 
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
#define pii pair<int,int>
#define LL long long
#define st first
#define nd second
#define endl '\n'
using namespace std;

const int MAXN=100005;
LL f[MAXN*4],lz[MAXN*4],n,x[MAXN],g[MAXN],d[MAXN],p[MAXN],ans;

int main() {

	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i=1;i<=n;++i) {
		cin>>x[i]>>g[i]>>d[i];
		d[i]+=d[i-1];
		g[i]+=g[i-1];
	}
	for(int i=n;i>=1;--i) {
		if(i==n) p[i]=d[i]-x[i];
		else p[i]=max(p[i+1],d[i]-x[i]);
	}
	for(int i=1;i<=n;++i) {
		int l=i,r=n+1,md;
		while(l+1<r) {
			md=(l+r)/2;
			if(p[md]>=d[i-1]-x[i])
				l=md;
			else r=md;
		}
		ans=max(ans,g[l]-g[i-1]);
	}
	cout<<ans<<endl;

}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 376 KB Output is correct
3 Correct 3 ms 392 KB Output is correct
4 Correct 2 ms 392 KB Output is correct
5 Correct 3 ms 480 KB Output is correct
6 Correct 3 ms 480 KB Output is correct
7 Correct 3 ms 496 KB Output is correct
8 Correct 3 ms 572 KB Output is correct
9 Correct 3 ms 620 KB Output is correct
10 Correct 3 ms 704 KB Output is correct
11 Correct 2 ms 704 KB Output is correct
12 Correct 3 ms 704 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 704 KB Output is correct
2 Correct 2 ms 704 KB Output is correct
3 Correct 3 ms 704 KB Output is correct
4 Correct 2 ms 704 KB Output is correct
5 Correct 3 ms 704 KB Output is correct
6 Correct 3 ms 704 KB Output is correct
7 Correct 4 ms 704 KB Output is correct
8 Correct 3 ms 704 KB Output is correct
9 Correct 3 ms 704 KB Output is correct
10 Correct 5 ms 704 KB Output is correct
11 Correct 6 ms 764 KB Output is correct
12 Correct 6 ms 768 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 768 KB Output is correct
2 Correct 6 ms 892 KB Output is correct
3 Correct 7 ms 892 KB Output is correct
4 Correct 25 ms 2196 KB Output is correct
5 Correct 35 ms 2196 KB Output is correct
6 Correct 54 ms 3708 KB Output is correct
7 Correct 38 ms 3708 KB Output is correct
8 Correct 42 ms 3708 KB Output is correct
9 Correct 39 ms 3712 KB Output is correct
10 Correct 55 ms 3712 KB Output is correct
11 Correct 53 ms 3712 KB Output is correct
12 Correct 43 ms 3712 KB Output is correct