oj.uz

Submission #141541

# Submission time Handle Problem Language Result Execution time Memory
141541 2019-08-08T10:46:09 Z meatrow Divide and conquer (IZhO14_divide) C++17
100 / 100
 58 ms 7544 KB 
//#pragma GCC optimize("O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
//#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

using ll = long long;


int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
    ll ans = 0;
    vector<ll> G(n + 1), E(n + 1), x(n + 1);
    vector<pair<ll, int>> kek(n);
    for (int i = 1; i <= n; i++) {
        ll g, d;
        cin >> x[i] >> g >> d;
        kek[i - 1] = { E[i - 1] - x[i], i - 1 };
        E[i] = E[i - 1] + d;
        G[i] = G[i - 1] + g;   
    }
    sort(kek.begin(), kek.end());
    vector<int> pref(n);
    pref[0] = kek[0].second;
    for (int i = 1; i < n; i++) {
        pref[i] = min(pref[i - 1], kek[i].second);
    }
    for (int i = 1; i <= n; i++) {
        int pos = upper_bound(kek.begin(), kek.end(), make_pair(E[i] - x[i], 0)) - kek.begin() - 1;
        if (pos >= 0 && pos < n) {
            ans = max(ans, G[i] - G[pref[pos]]);
        }
    }
    cout << ans;
    return 0; 
}

Subtask #1
17.0 / 17.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 380 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 3 ms 380 KB Output is correct
11 Correct 4 ms 632 KB Output is correct
12 Correct 4 ms 632 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 632 KB Output is correct
2 Correct 6 ms 892 KB Output is correct
3 Correct 6 ms 1016 KB Output is correct
4 Correct 26 ms 3448 KB Output is correct
5 Correct 29 ms 3832 KB Output is correct
6 Correct 58 ms 7544 KB Output is correct
7 Correct 46 ms 6364 KB Output is correct
8 Correct 47 ms 6520 KB Output is correct
9 Correct 45 ms 6264 KB Output is correct
10 Correct 46 ms 6264 KB Output is correct
11 Correct 50 ms 6776 KB Output is correct
12 Correct 51 ms 7032 KB Output is correct