oj.uz

Submission #114877

# Submission time Handle Problem Language Result Execution time Memory
114877 2019-06-03T18:36:35 Z mrboorger Bank (IZhO14_bank) C++14
0 / 100
 4 ms 2432 KB 
#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;
}

Compilation message

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

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2432 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2432 KB Output isn't correct
2 Halted 0 ms 0 KB -