Submission #479981

#	Time	Username	Problem	Language	Result	Execution time	Memory
479981		Dima_Borchuk	Divide and conquer (IZhO14_divide)	C++17	48 / 100	1080 ms	3300 KiB

divide

#pragma GCC optimize("Ofast")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define sz(x) int32_t(x.size())
#define pii pair < int, int >
#include <bits/stdc++.h>
#define ld long double
#define ll long long
#define _ << ' ' <<
#define se second
#define fi first
#define int ll

using namespace __gnu_pbds;
using namespace std;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

mt19937 gen(chrono::system_clock::now().time_since_epoch().count());

const int mod = (int)1e9 + 9;
const int N = (int)1e6 + 5;
const int INF = (int)1e16 + 5;

struct point {
    int x, g, e;
};

int32_t main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int n;
    cin >> n;
    vector < point > a(n + 1);
    vector < int > pe(n + 1, 0), pg(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> a[i].x >> a[i].g >> a[i].e;
        pe[i] = pe[i - 1] + a[i].e;
        pg[i] = pg[i - 1] + a[i].g;
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        for (int j = i; j <= n; j++) {
            if (pe[j] - pe[i - 1] >= a[j].x - a[i].x) {
                ans = max(ans, pg[j] - pg[i - 1]);
            }
        }
    }

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

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