Submission #1104525

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104525		ljtunas	Art Exhibition (JOI18_art)	C++17	100 / 100	188 ms	35656 KiB

art

// author : anhtun_hi , nqg
#include <bits/stdc++.h>
#define fi first
#define se second
#define all(x) x.begin(), x.end()
#define reset(h, v)    memset(h, v, sizeof h)
#define Forv(i, a)     for(auto& i : a)
#define For(i, a, b)   for(int i = a; i <= b; ++i)
#define Ford(i, a, b)  for(int i = a; i >= b; --i)
#define c_bit(i)     __builtin_popcountll(i)
#define Bit(mask, i)    ((mask >> i) & 1LL)
#define onbit(mask, i)  ((mask) bitor (1LL << i))
#define offbit(mask, i) ((mask) &~ (1LL << i))

using namespace std;
using ll = long long;
using ii = pair<ll, ll>;
using vi = vector<ll>;

void maximize(auto& a, auto b){a = max(a, b);}
void minimize(auto& a, auto b){a = min(a, b);}

//#define int long long

const int dx[] = {0, 0, +1, -1}, dy[] = {-1, +1, 0, 0};
const int MAXN = 1e6 + 10, LOG = 20, base = 311;
const int  inf = 1e9 + 5;
const  ll  mod = 1e9 + 7;
const  ll   oo = 1e18;

int n; ii a[MAXN]; ll f[MAXN];

void Solve(){
    cin >> n;
    For(i, 1, n) cin >> a[i].fi >> a[i].se;
    sort(a + 1, a + n + 1, greater<ii>());
    vector<ll> st(n * 2 + 5, +oo);
    auto update = [&](int i, ll val){
        for(st[i += n+1] = val; i > 1; i /= 2)
            st[i / 2] = min(st[i ^ 1], st[i]);
    };
    auto get = [&](int l, int r){
        ll res = oo;
        for(l+=n+1, r+=n+2; l < r; l/=2, r/=2){
            if(l & 1) minimize(res, st[l++]);
            if(r & 1) minimize(res, st[--r]);
        }
        return res;
    };
    ll ans = -oo;
    For(i, 1, n){
        f[i] = f[i - 1] + a[i].se;
        update(i, a[i].fi + f[i - 1]);
        maximize(ans, f[i] + a[i].fi - get(1, i));
    }
    cout << ans << '\n';
}

int32_t main(){
    cin.tie(0) -> sync_with_stdio(0);
    if(fopen("JOI18_art.inp", "r")){
       freopen("JOI18_art.inp", "r", stdin);
       freopen("JOI18_art.out", "w", stdout);
    }

    int t = 1;
//    cin >> t;

    for (int test = 1; test <= t; test++){
        Solve();
    }
    return 0;
}

Compilation message (stderr)

art.cpp:20:15: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void maximize(auto& a, auto b){a = max(a, b);}
      |               ^~~~
art.cpp:20:24: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   20 | void maximize(auto& a, auto b){a = max(a, b);}
      |                        ^~~~
art.cpp:21:15: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   21 | void minimize(auto& a, auto b){a = min(a, b);}
      |               ^~~~
art.cpp:21:24: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
   21 | void minimize(auto& a, auto b){a = min(a, b);}
      |                        ^~~~
art.cpp: In function 'int32_t main()':
art.cpp:62:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |        freopen("JOI18_art.inp", "r", stdin);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
art.cpp:63:15: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |        freopen("JOI18_art.out", "w", stdout);
      |        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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