Submission #951307

#	Time	Username	Problem	Language	Result	Execution time	Memory
951307		LOLOLO	Divide and conquer (IZhO14_divide)	C++17	0 / 100	2 ms	6492 KiB

divide

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

#define           f     first
#define           s     second
#define           pb    push_back
#define           ep    emplace
#define           eb    emplace_back
#define           lb    lower_bound
#define           ub    upper_bound
#define       all(x)    x.begin(), x.end()
#define      rall(x)    x.rbegin(), x.rend()
#define   uniquev(v)    sort(all(v)), (v).resize(unique(all(v)) - (v).begin())
#define     mem(f,x)    memset(f , x , sizeof(f))
#define        sz(x)    (int)(x).size()
#define  __lcm(a, b)    (1ll * ((a) / __gcd((a), (b))) * (b))
#define          mxx    *max_element
#define          mnn    *min_element
#define    cntbit(x)    __builtin_popcountll(x)
#define       len(x)    (int)(x.length())

const int N = 2e5 + 100;
ll seg[N * 4], dp[N];
int n;

void point(int id, int l, int r, int p, ll v) {
    if (l > p || r < p)
        return;

    seg[id] = max(seg[id], v);
    if (l == r)
        return;

    int m = (l + r) / 2;
    point(id * 2, l, m, p, v);
    point(id * 2 + 1, m + 1, r, p, v);
}

ll get(int id, int l, int r, int u, int v) {
    if (l > v || r < u)
        return -1e16;

    if (l >= u && r <= v)
        return seg[id];

    int m = (l + r) / 2;
    return max(get(id * 2, l, m, u, v), get(id * 2 + 1, m + 1, r, u, v));
}

ll x[N], g[N], d[N];

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;

    fill(seg, seg + n * 4 + 10, -1e16);
    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, int> mp;
    int timer = 1;
    for (int i = 1; i <= n; i++) {
        mp[x[i] - d[i - 1]];
        mp[x[i] - d[i]];
    }

    for (auto &x : mp)
        x.s = timer++;

    ll ans = 0;
    for (int i = 1; i <= n; i++) {
        int p = mp[x[i] - d[i]];
        ll t = g[i] + get(1, 1, n, p, n);
        dp[i] = max({dp[i - 1], t, g[i] - g[i - 1]});
        point(1, 1, n, mp[x[i] - d[i - 1]], dp[i - 1] - g[i - 1]);
        ans = max(ans, dp[i]);
    }

    cout << ans << '\n';
    return 0;
}

/*
en[i] = g[1] + g[2] +..+ g[i];
s[i] =  d[1] + d[2] +..+ d[i];
dp[i] = tổng lớn nhất.
dp[i] = max(dp[i - 1], dp[j - 1] + en[i] - en[j - 1]); 
(x[i] - x[j] <= s[i] - s[j - 1])
<=> x[i] - s[i] <= x[j] - s[j - 1]
*/

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