Submission #503249

#	Time	Username	Problem	Language	Result	Execution time	Memory
503249		blue	Divide and conquer (IZhO14_divide)	C++17	100 / 100	39 ms	8864 KiB

divide

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

using ll = long long;

const ll INF = 1'000'000'000'000'000'000LL;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    cin >> N;

    ll x[1+N], g[1+N], d[1+N];

    d[0] = 0;
    g[0] = 0;
    for(int i = 1; i <= N; i++)
    {
        cin >> x[i] >> g[i] >> d[i];
        d[i] += d[i-1];
        g[i] += g[i-1];
    }

    vector<pair<ll, ll> > A, B;
    A.push_back({-INF, -INF});
    B.push_back({-INF, -INF});
    for(int i = 1; i <= N; i++)
    {
        A.push_back({d[i] - x[i], g[i]});
        B.push_back({d[i-1] - x[i], - g[i-1]});

        // cerr << i << " : " << d[i] - x[i] << "," << g[i] << "  " << d[i-1]-x[i] << "," << -g[i-1] << '\n';
    }

    ll ans = 0;

    sort(A.begin(), A.end());
    sort(B.begin(), B.end());

    ll sa = -INF, sb = -INF;

    int a = 0, b = 0;
    for(a = 1; a <= N; a++)
    {
        // sa = max(sa, A[a].second);
        while(b+1 <= N && B[b+1].first <= A[a].first)
        {
            b++;
            sb = max(sb, B[b].second);
        }
        ans = max(ans, A[a].second+sb);
    }

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

Compilation message (stderr)

divide.cpp: In function 'int main()':
divide.cpp:45:8: warning: unused variable 'sa' [-Wunused-variable]
   45 |     ll sa = -INF, sb = -INF;
      |        ^~

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