Submission #958835

#	Time	Username	Problem	Language	Result	Execution time	Memory
958835		Maaxle	Art Exhibition (JOI18_art)	C++17	100 / 100	182 ms	86608 KiB

art

#include <bits/stdc++.h>

#define range(it, a, b) for (ll it = a; it < b; it++)
#define all(x) begin(x), end(x)
#define ll long long
#define ull unsigned long long
#define INF64 ((ll) 1 << 62)
#define INF32 (1 << 30)
#define mset multiset
#define uset unordered_set
#define umap unordered_map 
#define pqueue priority_queue 
#define ptr(A) shared_ptr<A>

using namespace std;

void setio (string name) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if (name.size()) {
        freopen((name + ".in").c_str(), "r", stdin);
        freopen((name + ".out").c_str(), "w", stdout);
    }
}

struct TPos {
    ll val, sz;
};

struct SegTree {
    struct Node {
        Node* left;
        Node* right;

        ll l, r, m;
        ll ans;
        ll sum;
        ll pre;
        ll suf;
    };

    Node* root;
    vector<TPos>& arr;

    SegTree (vector<TPos>& a) : arr(a) {
        root = new Node;
        root->l = 0;
        root->r = a.size() - 1;
        root->m = (a.size()-1)/2;
        build(root);
    }

    void build(Node* node) {
        if (node->l == node->r) {
            node->ans = arr[node->l].val;
            node->sum = node->ans;
            node->suf = node->sum + arr[node->l].sz;
            node->pre = node->sum - arr[node->l].sz;
            return;
        }

        node->left = new Node;
        node->left->l = node->l;
        node->left->r = node->m;
        node->left->m = (node->l + node->m)/2;
        build(node->left);

        node->right = new Node;
        node->right->l = node->m+1;
        node->right->r = node->r;
        node->right->m = (node->r + node->m+1)/2;
        build (node->right);

        node->ans = max({node->left->ans, node->right->ans, node->left->suf + node->right->pre});
        node->sum = node->left->sum + node->right->sum;
        node->pre = max(node->left->pre, node->left->sum + node->right->pre);
        node->suf = max(node->right->suf, node->right->sum + node->left->suf);
    }
};

ll n;
vector<TPos> arr;

void solve() {
    cin >> n;
    arr.resize(n);

    range(i, 0, n) 
        cin >> arr[i].sz >> arr[i].val;
    sort(all(arr), [](const TPos& a, const TPos& b) {
        return a.sz < b.sz;
    });

    SegTree st(arr);
    cout << st.root->ans;
}

int main () {
    setio("");
    ll t = 1; 
    // cin >> t;
    while (t--) solve();
}

// IT'S TOUGH, I KNOW
// BUT YOU'D RATHER DIE FIGHTING THAN LIVE ON YOUR KNEES
// THOUG H YOU WON'T DO NEITHER OF THOSE
// IMPOSSIBLE, AS IT'S AGAINST YOUR NATURE
// AS YOU ALREADY WON
// I SEE YOUR MEDAL HANGING FROM YOUR NECK
// SHINING AS NOTHING YOU'VE EVER HAD

// THOUSANDS AND THOUSANDS OF LINES
// YOU AREADY MADE IT THIS FAR
// AND WHO COULD TELL HOW FAR YOU WILL GET...
// BUT YOU?

// THEN COME ON, YOU BASTARD!
// GO CLEAR YOUR MIND AND STAND
// AS EACH OF THOSE LINES IS A STEP CLOSER
// CLOSER TO THE GREATNESS YOU PURSUE
// CLOSER TO THE GREATNESS YOU ALREADY HAVE

Compilation message (stderr)

art.cpp: In function 'void setio(std::string)':
art.cpp:21:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         freopen((name + ".in").c_str(), "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
art.cpp:22:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         freopen((name + ".out").c_str(), "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50