oj.uz

Submission #114876

# Submission time Handle Problem Language Result Execution time Memory
114876 2019-06-03T18:33:25 Z mrboorger Divide and conquer (IZhO14_divide) C++14
100 / 100
 40 ms 5912 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

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

Subtask #1
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2432 KB Output is correct
2 Correct 4 ms 2432 KB Output is correct
3 Correct 3 ms 2432 KB Output is correct
4 Correct 3 ms 2432 KB Output is correct
5 Correct 3 ms 2432 KB Output is correct
6 Correct 4 ms 2432 KB Output is correct
7 Correct 3 ms 2432 KB Output is correct
8 Correct 3 ms 2432 KB Output is correct
9 Correct 4 ms 2432 KB Output is correct
10 Correct 3 ms 2432 KB Output is correct
11 Correct 3 ms 2432 KB Output is correct
12 Correct 3 ms 2432 KB Output is correct

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2432 KB Output is correct
2 Correct 4 ms 2432 KB Output is correct
3 Correct 3 ms 2432 KB Output is correct
4 Correct 4 ms 2432 KB Output is correct
5 Correct 3 ms 2432 KB Output is correct
6 Correct 4 ms 2432 KB Output is correct
7 Correct 3 ms 2432 KB Output is correct
8 Correct 4 ms 2560 KB Output is correct
9 Correct 4 ms 2432 KB Output is correct
10 Correct 4 ms 2560 KB Output is correct
11 Correct 5 ms 2560 KB Output is correct
12 Correct 6 ms 2560 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2560 KB Output is correct
2 Correct 6 ms 2816 KB Output is correct
3 Correct 7 ms 2816 KB Output is correct
4 Correct 19 ms 3968 KB Output is correct
5 Correct 21 ms 4096 KB Output is correct
6 Correct 39 ms 5624 KB Output is correct
7 Correct 33 ms 5888 KB Output is correct
8 Correct 33 ms 5880 KB Output is correct
9 Correct 33 ms 5880 KB Output is correct
10 Correct 33 ms 5912 KB Output is correct
11 Correct 40 ms 5880 KB Output is correct
12 Correct 39 ms 5852 KB Output is correct