Submission #1240909

#	Time	Username	Problem	Language	Result	Execution time	Memory
1240909		_dtq_	Divide and conquer (IZhO14_divide)	C++20	0 / 100	0 ms	324 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 = 1e5 + 9;

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

vector<pair<ll,ll>>vec;

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

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

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

    ll sum = -1e18;

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

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

    return sum;
}

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;

    ll kq = 0;

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

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

        sum += z[i];
        vec.pb({sum - x[i], i});
        bit[i][0] = -1e18;
        bit[i][1] = -1e18;

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

    sort(all(vec));

    for(auto k : vec)
    {
        i = k.se;

        ll ans = get(i - 1, 0);

        ans += gold[i];

        ans = max(ans, get(i - 1, 1));

        ans = max(ans, 0LL);

        if(k.fi + x[i] >= (x[i] - x[1]))
            ans = max(ans, gold[i]);
        
        up(i, 1, ans);
        up(i, 0, max(0LL, get(i - 1, 1)) - gold[i - 1]);

        //cout << i << " " << ans << "\n";

    }

    cout << max(kq, get(n, 1));

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

 */

Compilation message (stderr)

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

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