Submission #519855

#	Time	Username	Problem	Language	Result	Execution time	Memory
519855		Lam_lai_cuoc_doi	Divide and conquer (IZhO14_divide)	C++17	100 / 100	46 ms	7472 KiB

divide

#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 (stderr)

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 / 17
• Subtask 2: 31 / 31
• Subtask 3: 52 / 52