Submission #255261

#	Time	Username	Problem	Language	Result	Execution time	Memory
255261		ttnhuy313	Divide and conquer (IZhO14_divide)	C++14	48 / 100	1090 ms	6648 KiB

divide

#include <bits/stdc++.h>

using namespace std;
#define int long long

const int N = 1e6 + 5, INF = 1e9 + 7;
int pref1[N], pref2[N], e[N], g[N], x[N];

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    
    int n, i, j, k, ans = 0;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> x[i] >> g[i] >> e[i];
        ans = max(ans, g[i]);
        pref1[i] = pref1[i - 1] + e[i];
        pref2[i] = pref2[i - 1] + g[i];
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = n; j >= i; --j) {
            if (ans >= pref2[j] - pref2[i - 1]) break;
            int z = x[j] - x[i], c = pref1[j] - pref1[i - 1];
            if (z <= c) {
                ans = pref2[j] - pref2[i - 1];
            }
        }
    }
    cout << ans << endl;
    return 0;

}

Compilation message (stderr)

divide.cpp: In function 'int main()':
divide.cpp:12:12: warning: unused variable 'i' [-Wunused-variable]
     int n, i, j, k, ans = 0;
            ^
divide.cpp:12:15: warning: unused variable 'j' [-Wunused-variable]
     int n, i, j, k, ans = 0;
               ^
divide.cpp:12:18: warning: unused variable 'k' [-Wunused-variable]
     int n, i, j, k, ans = 0;
                  ^

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