제출 #114870

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

divide

#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <iostream>
//#pragma GCC optimize("Ofast")

#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;

//mt19937 gen(time(0));
const ll inf = 1e18 + 18;
const int maxn = 100205;
const int cellsz = 317; // = cellcnt
const int maxc = 513; // = cellcnt


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

ll sum[maxn];
ll en[cellsz];

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

tree T[cellsz];

main()
{
#ifdef LOCAL
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#else
//    freopen("divide.in", "r", stdin);
//    freopen("divide.out", "w", stdout);
#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];
    }
    {
        for(int i = 0;(i + 1) * cellsz - 1 < n; i++)
        {
            T[i].build(i * cellsz - 1);
        }
    }
    ll ans = 0;
    for(int i = 0; i < n; i++)
    {
        int gg = 0;
        while((gg + 1) * cellsz - 1 <= i)
        {
            en[gg] += d[i];
            if (i > 0) en[gg] -= x[i] - x[i - 1];
            int uk = T[gg].fnd(-en[gg]);
            if (uk > -1)
            {
                ll val = sum[i];
                if (uk + gg * cellsz - 1 >+ 0) val -= sum[uk + gg * cellsz - 1];
                ans = max(ans, val);
            }
            gg++;
        }
        {
            gg--;
            ll sumen = d[i];
            ll sumg = g[i];
            ans = max(ans, sumg);
            for(int j = i - 1; j >= max(0, gg * cellsz - 1); j--)
            {
                sumen += d[j] - (x[j + 1] - x[j]);
                sumg += g[j];
                if (sumen >= 0)
                    ans = max(ans, sumg);
            }
        }
    }
    cout << ans;
    return 0;
}

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

divide.cpp:74: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