oj.uz

Submission #344598

# Submission time Handle Problem Language Result Execution time Memory
344598 2021-01-06T06:27:50 Z mansur Divide and conquer (IZhO14_divide) C++14
0 / 100
 1 ms 364 KB 
#include<bits/stdc++.h>
using namespace std;

#define all(a) a.begin(),a.end()
#define ll long long
#define pb push_back
#define nl '\n'
#define popb pop_back()
#define sz size()
#define ld long double
#define ull unsigned long long
#define F first
#define S second
#define fix fixed<<setprecision
#define pii pair<int,int>
#define E exit (0)
#define int long long
const int inf=1e9;
int n,x[100001],g[100001],d[100001];
pair<pii,pii> dq(int l,int r,int z=0) {
	if (l==r) {
		return {{g[l],d[l]},{x[l],x[l]}}; 
	}
	int mid=(l+r)/2;
	pair<pii,pii> a=dq(l,mid,1),b=dq(mid+1,r,2);
	if (b.S.S-a.S.F<=a.F.S+b.F.S) {
		return {{a.F.F+b.F.F,a.F.S+b.F.S},{a.S.F,b.S.S}};
	}
	if (z==2) {
		return a;
	}
	if (z==1) {
		return b;
	}
	if (a.F.F>=b.F.F) {
		return a;
	}
	return b;
}
signed main() {
	//freopen("planting.in","r",stdin);
	//freopen("planting.out","w",stdout);
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin>>n;
	for (int i=1;i<=n;i++) {
	 	cin>>x[i]>>g[i]>>d[i];
	}
	cout<<dq(1,n).F.F;
}

Subtask #1
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Incorrect 0 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Incorrect 0 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Incorrect 0 ms 364 KB Output isn't correct
5 Halted 0 ms 0 KB -