Submission #590692

#	Time	Username	Problem	Language	Result	Execution time	Memory
590692		fuad27	Divide and conquer (IZhO14_divide)	C++17	100 / 100	133 ms	11752 KiB

divide

/*
 * Created: 2022-07-06 11:21
*/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace __gnu_pbds;
using namespace std;
using namespace chrono;
// using namespace atcoder

template <typename T>
using ordered_set =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
const ll inf = 1e18;

#define pii		pair<int,int>
#define pll		pair<ll,ll>
#define vi		vector<int>
#define vll		vector<ll>
#define rep(i, a, b)	for(int i = (a);i<(b);i++)
#define repn(i, a, b)	for(int i = (a);i>=(b);i--)
#define ss		second
#define ff		first
#define mkp		make_pair
#define pb		push_back

#define all(x)		(x).begin(), (x).end()
const int N = 100010;
long long g[N];
long long d[N];
long long x[N];

long long dv(int l, int r) {
	if(l == r) {
		return g[l];
	}
	ll ans2 = 0;
	int mid = (l+r)/2;
	map<ll, ll> mp;
	int prev = x[mid+1];
	long long sumg=0;
	long long sum=0;
	for(int i = mid+1;i<=r;i++) {
		sum+=d[i];
		sumg+=g[i];
		mp[sum-(x[i]-prev)]=sumg+1;
	}
	for(auto i = mp.rbegin();i!=mp.rend();++i) {
		auto it = i;
		++it;
		if(it!=mp.rend()) {
			(*it).second=max((*i).second, (*it).second);
		}
	}
	long long ans = 0;
	sumg=0;
	sum=0;
	prev=x[mid+1];
	for(int i = mid;i>=l;i--) {
		sum+=d[i];
		sumg+=g[i];
		auto it = mp.lower_bound(-sum+(prev-x[i]));
		if(it==mp.end())continue;
		ans=max(ans, sumg+(*it).second-1);
	}
	ans2=max(dv(l, mid), dv(mid+1, r));
	return max(ans2, ans);
}
void solve() {
	int n;
	cin >> n;
	for(int i = 0;i<n;i++) {
		cin >> x[i] >> g[i] >> d[i];
	}
	cout << dv(0, n-1) << "\n";
}

int main () {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t = 1;
	while(t--) {
		solve();
	}
	return 0;
}

• Subtask 1: 17 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52