oj.uz

Submission #519855

# Submission time Handle Problem Language Result Execution time Memory
519855 2022-01-27T12:38:19 Z Lam_lai_cuoc_doi Divide and conquer (IZhO14_divide) C++17
100 / 100
 46 ms 7472 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

template <class T>
void read(T &x)
{
    x = 0;
    register int c;
    while ((c = getchar()) && (c > '9' || c < '0'))
        ;
    for (; c >= '0' && c <= '9'; c = getchar())
        x = x * 10 + c - '0';
}

constexpr bool typetest = 0;
constexpr int N = 1e5 + 5;
constexpr ll Inf = 1e17;

struct FenwickMaxTree
{
    int n;
    ll a[N];

    FenwickMaxTree()
    {
        fill_n(a, N, -Inf);
    }

    void Update(int p, ll v)
    {
        for (; p <= n; p += p & -p)
            a[p] = max(a[p], v);
    }

    ll Get(int p)
    {
        ll ans(-Inf);

        for (; p; p -= p & -p)
            ans = max(ans, a[p]);

        return ans;
    }
} f;

int n;
struct miningcamp
{
    int x;
    ll g, e;
    miningcamp(int x = 0, ll g = 0, ll e = 0) : x(x), g(g), e(e) {}

    bool operator<(const miningcamp &a) const
    {
        return x < a.x;
    }
} a[N];

void Read()
{
    cin >> n;

    for (int i = 1; i <= n; ++i)
        cin >> a[i].x >> a[i].g >> a[i].e;
}

void Solve()
{
    sort(a + 1, a + n + 1);

    vector<ll> s;

    for (int i = 1; i <= n; ++i)
    {
        a[i].e += a[i - 1].e;
        a[i].g += a[i - 1].g;

        s.emplace_back(a[i - 1].e - a[i].x);
    }

    sort(s.begin(), s.end());
    s.resize(unique(s.begin(), s.end()) - s.begin());
    f.n = s.size();

    ll ans(0);

    for (int i = 1; i <= n; ++i)
    {
        int j = lower_bound(s.begin(), s.end(), a[i - 1].e - a[i].x) - s.begin() + 1;
        f.Update(j, -a[i - 1].g);

        j = lower_bound(s.begin(), s.end(), a[i].e - a[i].x + 1) - s.begin();

        ans = max(ans, f.Get(j) + a[i].g);
    }

    cout
        << ans;
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    if (fopen("tests.inp", "r"))
    {
        freopen("test.inp", "r", stdin);
        freopen("test.out", "w", stdout);
    }
    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        // cout << "Case " << _ << ": ";
        Read();
        Solve();
    }
    cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n";
}

/*
 */

Compilation message

divide.cpp: In function 'void read(T&)':
divide.cpp:12:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   12 |     register int c;
      |                  ^
divide.cpp: In function 'int32_t main()':
divide.cpp:112:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  112 |         freopen("test.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
divide.cpp:113:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  113 |         freopen("test.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
17.0 / 17.0

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

Subtask #2
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3404 KB Output is correct
2 Correct 2 ms 3404 KB Output is correct
3 Correct 2 ms 3404 KB Output is correct
4 Correct 2 ms 3404 KB Output is correct
5 Correct 2 ms 3404 KB Output is correct
6 Correct 2 ms 3404 KB Output is correct
7 Correct 2 ms 3404 KB Output is correct
8 Correct 3 ms 3404 KB Output is correct
9 Correct 2 ms 3404 KB Output is correct
10 Correct 2 ms 3404 KB Output is correct
11 Correct 2 ms 3404 KB Output is correct
12 Correct 2 ms 3404 KB Output is correct
13 Correct 2 ms 3404 KB Output is correct
14 Correct 2 ms 3404 KB Output is correct
15 Correct 2 ms 3404 KB Output is correct
16 Correct 2 ms 3404 KB Output is correct
17 Correct 3 ms 3404 KB Output is correct
18 Correct 2 ms 3404 KB Output is correct
19 Correct 2 ms 3416 KB Output is correct
20 Correct 2 ms 3404 KB Output is correct
21 Correct 2 ms 3404 KB Output is correct
22 Correct 2 ms 3404 KB Output is correct
23 Correct 4 ms 3440 KB Output is correct
24 Correct 4 ms 3532 KB Output is correct

Subtask #3
52.0 / 52.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3404 KB Output is correct
2 Correct 2 ms 3404 KB Output is correct
3 Correct 2 ms 3404 KB Output is correct
4 Correct 2 ms 3404 KB Output is correct
5 Correct 2 ms 3404 KB Output is correct
6 Correct 2 ms 3404 KB Output is correct
7 Correct 2 ms 3404 KB Output is correct
8 Correct 3 ms 3404 KB Output is correct
9 Correct 2 ms 3404 KB Output is correct
10 Correct 2 ms 3404 KB Output is correct
11 Correct 2 ms 3404 KB Output is correct
12 Correct 2 ms 3404 KB Output is correct
13 Correct 2 ms 3404 KB Output is correct
14 Correct 2 ms 3404 KB Output is correct
15 Correct 2 ms 3404 KB Output is correct
16 Correct 2 ms 3404 KB Output is correct
17 Correct 3 ms 3404 KB Output is correct
18 Correct 2 ms 3404 KB Output is correct
19 Correct 2 ms 3416 KB Output is correct
20 Correct 2 ms 3404 KB Output is correct
21 Correct 2 ms 3404 KB Output is correct
22 Correct 2 ms 3404 KB Output is correct
23 Correct 4 ms 3440 KB Output is correct
24 Correct 4 ms 3532 KB Output is correct
25 Correct 3 ms 3532 KB Output is correct
26 Correct 6 ms 3580 KB Output is correct
27 Correct 6 ms 3580 KB Output is correct
28 Correct 20 ms 4048 KB Output is correct
29 Correct 27 ms 5336 KB Output is correct
30 Correct 46 ms 7472 KB Output is correct
31 Correct 37 ms 6224 KB Output is correct
32 Correct 39 ms 6368 KB Output is correct
33 Correct 41 ms 6224 KB Output is correct
34 Correct 42 ms 6212 KB Output is correct
35 Correct 40 ms 6744 KB Output is correct
36 Correct 41 ms 6868 KB Output is correct