oj.uz

Submission #42486

# Submission time Handle Problem Language Result Execution time Memory
42486 2018-02-27T17:21:42 Z MatheusLealV Divide and conquer (IZhO14_divide) C++14
100 / 100
 44 ms 9160 KB 
#include <bits/stdc++.h>
#define inf 2000000000000000000LL
#define N 200050
#define f first
using namespace std;
typedef long long ll;
 
ll cnt = 2;
 
ll n, sum[N], g[N], x[N], E[N], dp[N], ans, pref[N];
 
int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
 
	cin>>n;
 
	for(int i = 1; i <= n; i++)
	{
		cin>>x[i]>>g[i]>>E[i];
 
		sum[i] = E[i] + sum[i - 1];
 
		g[i] += g[i - 1];
	}

	pref[0] = inf;
  
	for(int i = 1; i <= n; ++i) pref[i] = min(pref[i - 1], sum[i - 1] - x[i]);

	for(int i = 1; i <= n; i++)
	{
		int ini = 1, fim = i, mid, best = i;

		while(fim >= ini)
		{
			mid = (ini + fim)/2;

			if(pref[mid] <= sum[i] - x[i]) best = mid, fim = mid - 1;

			else ini = mid + 1;
		}

		ans = max(ans, g[i] - g[best - 1]);
	}
 
	cout<<ans<<"\n";
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 424 KB Output is correct
4 Correct 1 ms 460 KB Output is correct
5 Correct 2 ms 540 KB Output is correct
6 Correct 2 ms 540 KB Output is correct
7 Correct 2 ms 540 KB Output is correct
8 Correct 2 ms 540 KB Output is correct
9 Correct 2 ms 600 KB Output is correct
10 Correct 2 ms 600 KB Output is correct
11 Correct 2 ms 600 KB Output is correct
12 Correct 2 ms 600 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 2 ms 604 KB Output is correct
3 Correct 2 ms 676 KB Output is correct
4 Correct 2 ms 676 KB Output is correct
5 Correct 2 ms 676 KB Output is correct
6 Correct 2 ms 676 KB Output is correct
7 Correct 2 ms 676 KB Output is correct
8 Correct 2 ms 676 KB Output is correct
9 Correct 2 ms 676 KB Output is correct
10 Correct 2 ms 676 KB Output is correct
11 Correct 4 ms 748 KB Output is correct
12 Correct 3 ms 748 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 748 KB Output is correct
2 Correct 5 ms 1004 KB Output is correct
3 Correct 5 ms 1004 KB Output is correct
4 Correct 19 ms 2548 KB Output is correct
5 Correct 21 ms 2548 KB Output is correct
6 Correct 44 ms 4460 KB Output is correct
7 Correct 38 ms 4460 KB Output is correct
8 Correct 35 ms 4492 KB Output is correct
9 Correct 32 ms 4492 KB Output is correct
10 Correct 37 ms 4588 KB Output is correct
11 Correct 40 ms 6892 KB Output is correct
12 Correct 42 ms 9160 KB Output is correct