Submission #195614

#	Time	Username	Problem	Language	Result	Execution time	Memory
195614		jovan_b	Divide and conquer (IZhO14_divide)	C++17	100 / 100	57 ms	7400 KiB

divide

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll g[100005];
ll x[100005];
ll d[100005];
ll xx[100005];

int main(){
    ios_base::sync_with_stdio(false);

    int n;
    cin >> n;
    vector <pair <ll, int>> tren;
    ll sum = 0;
    for(int i=1; i<=n; i++){
        cin >> xx[i] >> g[i] >> d[i];
        x[i] = xx[i]-xx[1];
        g[i] += g[i-1];
        d[i] += d[i-1];
        sum = max(sum, g[i]-g[i-1]);
        int l=0, r=tren.size()-1, j=i;
        while(l <= r){
            int mid = (l+r)/2;
            if(tren[mid].first-x[i]+d[i] >= 0){
                r = mid-1;
                j = mid;
            }
            else l = mid+1;
        }
        if(j < tren.size()) sum = max(sum, g[i]-g[tren[j].second-1]);
        if(tren.empty() || tren.back().first < x[i]-d[i-1]) tren.push_back({x[i]-d[i-1], i});
    }
    cout << sum << "\n";
    return 0;
}

Compilation message (stderr)

divide.cpp: In function 'int main()':
divide.cpp:33:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if(j < tren.size()) sum = max(sum, g[i]-g[tren[j].second-1]);
            ~~^~~~~~~~~~~~~

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