oj.uz

Submission #114875

# Submission time Handle Problem Language Result Execution time Memory
114875 2019-06-03T18:32:45 Z mrboorger Divide and conquer (IZhO14_divide) C++14
48 / 100
 40 ms 6392 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 = 163840;

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 2944 KB Output is correct
2 Correct 4 ms 2944 KB Output is correct
3 Correct 4 ms 2944 KB Output is correct
4 Correct 4 ms 2944 KB Output is correct
5 Correct 4 ms 2944 KB Output is correct
6 Correct 4 ms 2944 KB Output is correct
7 Correct 4 ms 2944 KB Output is correct
8 Correct 4 ms 2944 KB Output is correct
9 Correct 4 ms 2944 KB Output is correct
10 Correct 4 ms 2944 KB Output is correct
11 Correct 4 ms 2944 KB Output is correct
12 Correct 4 ms 2944 KB Output is correct

Subtask #2
31.0 / 31.0

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

Subtask #3
0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3072 KB Output is correct
2 Correct 6 ms 3400 KB Output is correct
3 Correct 7 ms 3428 KB Output is correct
4 Correct 23 ms 4920 KB Output is correct
5 Correct 22 ms 4864 KB Output is correct
6 Incorrect 40 ms 6392 KB Output isn't correct
7 Halted 0 ms 0 KB -