oj.uz

Submission #114870

# Submission time Handle Problem Language Result Execution time Memory
114870 2019-06-03T17:44:19 Z mrboorger Divide and conquer (IZhO14_divide) C++14
100 / 100
 345 ms 9072 KB 
#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;
}

Compilation message

divide.cpp:74: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 3 ms 1664 KB Output is correct
2 Correct 3 ms 1664 KB Output is correct
3 Correct 3 ms 1664 KB Output is correct
4 Correct 3 ms 1664 KB Output is correct
5 Correct 2 ms 1664 KB Output is correct
6 Correct 3 ms 1664 KB Output is correct
7 Correct 3 ms 1664 KB Output is correct
8 Correct 3 ms 1664 KB Output is correct
9 Correct 3 ms 1664 KB Output is correct
10 Correct 3 ms 1664 KB Output is correct
11 Correct 3 ms 1664 KB Output is correct
12 Correct 3 ms 1664 KB Output is correct

Subtask #2
31.0 / 31.0

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

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 1920 KB Output is correct
2 Correct 13 ms 2176 KB Output is correct
3 Correct 14 ms 2192 KB Output is correct
4 Correct 102 ms 4860 KB Output is correct
5 Correct 106 ms 5240 KB Output is correct
6 Correct 337 ms 9072 KB Output is correct
7 Correct 338 ms 7928 KB Output is correct
8 Correct 345 ms 7900 KB Output is correct
9 Correct 334 ms 7800 KB Output is correct
10 Correct 128 ms 7944 KB Output is correct
11 Correct 156 ms 8568 KB Output is correct
12 Correct 133 ms 8568 KB Output is correct