Submission #1241016

#	Time	Username	Problem	Language	Result	Execution time	Memory
1241016		_dtq_	Divide and conquer (IZhO14_divide)	C++17	100 / 100	50 ms	9148 KiB

divide

#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define sz(x) (ll)(x.size())
#define all(v) v.begin(), v.end()
#define sz(x) (ll)(x.size())
#define se second
#define fi first
using namespace std;

const ll N = 4e5 + 9;

ll n, i, x[N], y[N], z[N], pre[N], bit[N], gold[N];

void up(ll x, ll val)
{
    while(x <= n * 4)
    {
        bit[x] = max(bit[x], val);

        x += (x & (-x));
    }
}

ll get( ll x )
{
    if(x == 0) return 0;

    ll sum = -1e18;

    while(x > 0)
    {
        sum = max(sum, bit[x]);

        x -= (x & (-x));
    }

    return sum;
}

vector<ll>vec;



int main()
{
#define TN "divide"

    if (fopen(TN ".in", "r"))
    {
        freopen(TN ".in", "r", stdin);
        freopen(TN ".out", "w", stdout);
    }

    cin.tie(0)->sync_with_stdio(0);

    cin >> n;

    ll sum = 0;

    for( i = 1; i <= n; i ++ )
    {
        cin >> x[i] >> y[i] >> z[i];

        pre[i] = pre[i - 1] + z[i];

        gold[i] = gold[i - 1] + y[i];

        vec.pb(pre[i] - x[i]);

        vec.pb(pre[i - 1] - x[i]);
    }

    for( i = 1; i <= n * 4; i ++ ) bit[i] = -1e18;
    
    vec.pb(-1e18);

    sort(all(vec));

    ll kq = 0;

    ll maxn = 0, save = 0;

    for( i = 1; i <= n; i ++ )
    {
        ll k = pre[i] - x[i];
        ll vt = lower_bound(all(vec), k) - vec.begin();

        ll ans = get(vt);

        ll old = max(ans, 0LL);

        ans += gold[i];

        kq = max({kq, y[i], ans});

        old -= gold[i - 1];

        vt = lower_bound(all(vec), pre[i - 1] - x[i]) - vec.begin();

        up(vt, old);
    }

    cout << kq;

    return 0;
}
/*
6
0 5 1
1 7 2
4 4 1
7 15 1
8 15 0
10 15 2

5
1 1 1
2 1 1
3 1 1
4 1 1
5 1 1

 */

Compilation message (stderr)

divide.cpp: In function 'int main()':
divide.cpp:51:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         freopen(TN ".in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
divide.cpp:52:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         freopen(TN ".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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