Submission #334246

#	Time	Username	Problem	Language	Result	Execution time	Memory
334246		limabeans	Divide and conquer (IZhO14_divide)	C++17	100 / 100	104 ms	11140 KiB

divide

#include <bits/stdc++.h>
using namespace std;

template<typename T>
void out(T x) { cout << x << endl; exit(0); }
#define watch(x) cout << (#x) << " is " << (x) << endl





using ll = long long;


const int maxn = 1e6 + 5;


int n;
ll x[maxn], g[maxn], d[maxn];

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);  cout.tie(0);
    cin>>n;
    for (int i=1; i<=n; i++) {
	cin>>x[i]>>g[i]>>d[i];
	g[i]+=g[i-1];
	d[i]+=d[i-1];
    }




    map<ll,ll> mp; // mono-decreasing

    auto insert = [&](ll k, ll v) {
	auto iter = mp.lower_bound(k);

	// inserting v is useless
	if (iter != mp.end() && iter->second >= v) {
	    return;
	}

	mp[k] = v;
	iter = mp.lower_bound(k);
	
	if (iter == mp.begin()) return;
	--iter;
	
	while (true) {
	    if (iter->second > v) break;
	    auto it2 = iter;
	    bool done = false;
	    if (it2==mp.begin()) {
		done=true;
	    } else {
		--it2;
	    }
	    mp.erase(iter);
	    if (done) break;
	    iter = it2;
	}
    };

    auto check = [&]() {
	ll last = 1e18;
	for (auto p: mp) {
	    if (p.second > last) return false;
	    last = p.second;
	}
	return true;
    };

    ll ans = 0;

    for (int i=1; i<=n; i++) {
	insert(x[i]-d[i-1], -g[i-1]);
	auto iter = mp.lower_bound(x[i]-d[i]);
	if (iter != mp.end()) {
	    ans = max(ans, g[i]+iter->second);
	}
	//assert(check());
    }

    cout<<ans<<endl;
    return 0;
}

Compilation message (stderr)

divide.cpp: In function 'int main()':
divide.cpp:64:10: warning: variable 'check' set but not used [-Wunused-but-set-variable]
   64 |     auto check = [&]() {
      |          ^~~~~

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