oj.uz

Submission #113695

# Submission time Handle Problem Language Result Execution time Memory
113695 2019-05-27T19:21:10 Z ioilolcom Divide and conquer (IZhO14_divide) C++14
100 / 100
 46 ms 3960 KB 
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
typedef long long int ll;
struct camp {
	int x,g,d;
};
vector<camp> v;
const int N=1e6+7;
ll p[N];
ll sum[N];
ll lol[N];
int main()
{

	ios_base:: sync_with_stdio(false); cin.tie(0);
	int n; cin>>n;
	v.resize(n+1);
	//   doing presum for all things
	for(int i=1; i<=n; i++) {
		cin>>v[i].x>>v[i].g>>v[i].d;
		p[i]=p[i-1]+v[i].d;
		sum[i]=sum[i-1]+v[i].g;
		lol[i]=p[i]-v[i].x;
	}

	// to take gold from  between i and j we should have :
	// v[j].x-v[i].x<=p[j]-p[i-1]
//  <=> p[i-1]-v[i].x<=p[j]-v[j].x
	// to be able to do binary search for each i the max j>i such as the above condition is correct
	// we add this such as if the condition is holding at index j for example then we will try to make true for every index before it to fo binary-search
	// for example if the   we the condition is true at index j but not true at j-1  we will make true then with bs we will reach j by that
	for(int i=n-1; i>=1; i--) {
		lol[i]=max(lol[i],lol[i+1]);
	}
	ll ans=0;
	for(int i=1; i<=n; i++) {
		int me=p[i-1]-v[i].x;
		int l=i;
		int r=n;
		ans=max(ans,sum[i]-sum[i-1]);
		while(l<=r) {
			int mid=(l+r)/2;
			if(lol[mid]>=me) {
				ans=max(ans,sum[mid]-sum[i-1]);
				l=mid+1;
			}
			else{
				r=mid-1;
			}
		}

	}
	cout<<ans<<endl;

	return 0;
}

Subtask #1
17.0 / 17.0

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

Subtask #2
31.0 / 31.0

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

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 4 ms 768 KB Output is correct
3 Correct 5 ms 640 KB Output is correct
4 Correct 19 ms 2176 KB Output is correct
5 Correct 21 ms 2176 KB Output is correct
6 Correct 46 ms 3832 KB Output is correct
7 Correct 33 ms 3832 KB Output is correct
8 Correct 35 ms 3832 KB Output is correct
9 Correct 32 ms 3880 KB Output is correct
10 Correct 34 ms 3960 KB Output is correct
11 Correct 37 ms 3832 KB Output is correct
12 Correct 37 ms 3960 KB Output is correct