oj.uz

Submission #916770

# Submission time Handle Problem Language Result Execution time Memory
916770 2024-01-26T13:47:27 Z atom Divide and conquer (IZhO14_divide) C++17
17 / 100
 1 ms 2516 KB 
#include "bits/stdc++.h"
// @JASPER'S BOILERPLATE
using namespace std;
using ll = long long;

#ifdef JASPER
#include "debug.h"
#else
#define debug(...) 166
#endif

const int N = 2e5 + 5;

template <typename T>
struct FenwickTree {
    vector <T> f;
    int n;
    FenwickTree(int _n){
        init(_n);
    }
    void init(int _n) {
        n = _n;
        f.assign(n + 5, -1e18);
    }
    void upd(int x, ll val) {
        for (; x <= n; x += x & (-x))
            f[x] = max(f[x], val);
    }
    ll qry(int x) {
        ll ans = -1e18;
        for (; x > 0; x -= x & (-x))
            ans = max(ans, f[x]);
        return ans;
    }
};

int n;
int x[N], g[N], e[N];
ll prfE[N], prfG[N], dp[N];

signed main() {
    cin.tie(0) -> sync_with_stdio(0);

    cin >> n;
    for (int i = 1; i <= n; ++i) cin >> x[i] >> g[i] >> e[i];

    vector <ll> vals;
    for (int i = 1; i <= n; ++i) {
        prfG[i] = prfG[i - 1] + g[i];
        prfE[i] = prfE[i - 1] + e[i];
        vals.push_back(prfE[i] - x[i]);
        vals.push_back(prfE[i - 1] - x[i]);
        // xi - xj <= fe(i) - fe(j - 1) -> fe(i) - xi >= fe(j - 1) - xj
        // dp(i) = dp(j) + f(j + 1, i) = f(i) + max(dp(j) - f(j));
    }

    sort(vals.begin(), vals.end());
    vals.resize(unique(vals.begin(), vals.end()) - vals.begin());

    auto get = [&] (ll tar) {
        return (int) (lower_bound(vals.begin(), vals.end(), tar) - vals.begin() + 1);
    };

    FenwickTree <ll> fen((int) vals.size());
    for (int i = 1; i <= n; ++i) {
        ll p = get(prfE[i] - x[i]);
        dp[i] = max(1LL * g[i], prfG[i] + fen.qry(p));
        ll _p = get(prfE[i - 1] - x[i]); 
        fen.upd(_p, dp[i] - prfG[i]);
    }
    cout << (*max_element(dp + 1, dp + 1 + n)) << "\n";
}

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2512 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2516 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct

Subtask #2
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2512 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2516 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Incorrect 1 ms 2396 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2396 KB Output is correct
3 Correct 1 ms 2512 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 2396 KB Output is correct
6 Correct 1 ms 2396 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2396 KB Output is correct
9 Correct 1 ms 2516 KB Output is correct
10 Correct 1 ms 2396 KB Output is correct
11 Correct 1 ms 2396 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2392 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Incorrect 1 ms 2396 KB Output isn't correct
16 Halted 0 ms 0 KB -