Submission #784656

#	Time	Username	Problem	Language	Result	Execution time	Memory
784656		Alfraganus	Art Exhibition (JOI18_art)	C++14	100 / 100	434 ms	29112 KiB

art

#include <bits/stdc++.h>
// #include <ext/pb_ds/assoc_container.hpp>
using namespace std;
// using namespace __gnu_pbds;

// typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;

#define ll long long
#define str string
#define fastio ios::sync_with_stdio(0), cin.tie(0);
#define fs first
#define ss second
#define endl '\n'
#define all(x) (x).begin(), (x).end()
#define len(x) x.size()

#define print(a)          \
    for (auto &x : a)     \
        cout << x << " "; \
    cout << endl;

#define printmp(a)    \
    for (auto &x : a) \
        cout << x.fs << " " << x.ss << endl;

const int mod = 1e9 + 7;
const long long INF = LLONG_MAX;
const long long NEG_INF = LLONG_MIN;

void solve()
{
    int n;
    cin>>n;
    vector<pair<ll, ll>> a(n);
    for(int i = 0; i < n; i ++)cin>>a[i].fs >> a[i].ss;
    sort(all(a), greater<pair<ll, ll>> ());
    vector<pair<ll, ll>> b;
    int i = 0;
    while(i < n){
        ll s = a[i].ss;
        while(i < n and a[i].fs == a[i + 1].fs)s += a[++ i].ss;
        b.push_back({a[i].fs, s});
        i ++;
    }
    b.push_back({b.back().fs, 0});
    reverse(all(b));
    ll ans = 0, sum = 0;
    for(int i = 1; i < (int)b.size(); i ++){
        sum = max(b[i].ss, sum + b[i].ss + (b[i - 1].fs - b[i].fs));
        ans = max(ans, sum);
    }
    cout<<ans;
}

signed main()
{
    // fastio
    int t = 1;
    // cin >> t;
    while (t--)
    {
        solve();
        cout << endl;
    }
}

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