제출 #114876

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
114876		mrboorger	금 캐기 (IZhO14_divide)	C++14	100 / 100	40 ms	5912 KiB

divide

#include <bits/stdc++.h>

#define ld long double
#define ll long long
#define F first
#define S second
#define pb push_back
#define mp make_pair

using namespace std;

const ll inf = 1e18 + 18;
const int maxn = 131072;

ll x[maxn];
ll g[maxn];
ll d[maxn];
ll sum[maxn];

struct tree
{
    ll t[maxn * 2 + 2];
    ll se = 0;
    void build(int n)
    {
        for(int i = 0; i < n; i++)
        {
            se += d[i];
            t[i + maxn] = se - (x[i] - x[0]);
        }
        for(int i = n; i < maxn; i++)
            t[i + maxn] = -inf;
        for(int i = maxn - 1; i >= 1; i--)
            t[i] = max(t[i << 1], t[i << 1 | 1]);
        return;
    }
    int fnd(ll x)
    {
        int v = 1;
        while(v < maxn)
        {
            if (t[v << 1 | 1] >= x)
                v = v << 1 | 1;
            else
            if (t[v << 1] >= x)
                v = v << 1;
            else
                return -1;
        }
        return v - maxn;
    }
};

tree T;

main()
{
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n;
    cin >> n;
    for(int i = 0; i < n; i++)
    {
        cin >> x[i] >> g[i] >> d[i];
        if (i == 0) sum[i] = g[i];
            else    sum[i] = sum[i - 1] + g[i];
    }
    T.build(n);
    ll ans = 0;
    ll en = 0;
    for(int i = 0; i < n; i++)
    {
        if (i > 0)
        {
            en = en - d[i - 1] + (x[i] - x[i - 1]);
        }
        int uk = T.fnd(-en);
        if (uk > -1)
        {
            ll val = sum[uk];
            if (i > 0) val -= sum[i - 1];
            ans = max(ans, val);
        }
    }
    cout << ans;
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

divide.cpp:56:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main()
      ^

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