Submission #502771

#	Time	Username	Problem	Language	Result	Execution time	Memory
502771		LucaIlie	Divide and conquer (IZhO14_divide)	C++17	48 / 100	1014 ms	1872 KiB

divide

#include <iostream>

#define MAX_N 100000

using namespace std;


int x[MAX_N + 1], g[MAX_N + 1], d[MAX_N + 1];

int main() {
    int n, i, j;
    long long sg, sd, maxG;

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

    maxG = 0;
    for ( i = 1; i <= n; i++ ) {
        sg = sd = 0;
        for ( j = i; j <= n; j++ ) {
            sg += g[j];
            sd += d[j];
            if ( x[j] - x[i] <= sd ) {
                if ( sg > maxG )
                    maxG = sg;
            }
        }
    }

    cout << maxG;

    return 0;
}

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