Submission #867680

#	Time	Username	Problem	Language	Result	Execution time	Memory
867680		sleepntsheep	Divide and conquer (IZhO14_divide)	C++17	100 / 100	39 ms	5724 KiB

divide

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>
#include <set>
#include <utility>
#include <array>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,tune=native")
using namespace std;
#define ALL(x) x.begin(), x.end()
#define ShinLena cin.tie(nullptr)->sync_with_stdio(false);
using ll = long long;
#define N 100005
#define M 2*N
int n, x[N]; ll g[N], d[N], c[M], C, fw[M], z;
inline void upd(int p, ll k) { for (; p; p-=p&-p) fw[p] = max(fw[p], k); }
inline void qry(int p, ll g) { for (; p<M; p+=p&-p) z = max(z, fw[p] - g); }
int main()
{
    ShinLena;
    for (int i = (cin >> n, 0); i++ < n; ) cin >> x[i] >> g[i] >> d[i], d[i] += d[i-1], g[i] += g[i-1], c[C++] = d[i] - x[i], c[C++] = d[i-1] - x[i];
    sort(c, c+C);
    for (int i = n; i >= 1; --i) upd(lower_bound(c, c+C, d[i] - x[i]) - c + 1, g[i]), qry(lower_bound(c, c+C, d[i-1] - x[i] ) - c + 1, g[i-1]);
    cout << z;
    return 0;
}

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