Submission #1189669

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189669		starida1945	Art Exhibition (JOI18_art)	C++20	100 / 100	106 ms	12104 KiB

art

#pragma GCC optimize("O3")
#include <bits/stdc++.h>
//Und der Haifisch der hat tränen
//Und die laufen vom Gesicht
//Doch der Haifisch lebt im wasser
//So die Tränen sieht man nicht ಥ_ಥ

using namespace std;
#define ll long long
#define enter ios_base::sync_with_stdio(0); cin.tie(0)
#define dl long double
#define pb push_back
#define str string
#define endl '\n'
#define ENDL endl
#define all(v) v.begin(),v.end()
#define S second
#define F first
const ll sz = 5e5 + 10;
const ll mod = 1e9 + 7;

/*
Starida1945 presents:
───▄▀▀▀▄▄▄▄▄▄▄▀▀▀▄───
───█▒▒░░░░░░░░░▒▒█───
────█░░█░░░░░█░░█────
─▄▄──█░░░▀█▀░░░█──▄▄─
█░░█─▀▄░░░░░░░▄▀─█░░█
█▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀▀█
*/

pair<ll,ll> a[sz];

void sdksjdksj(){
    enter;

    ll n, ans = 0;
    cin>>n;

    for(ll i = 1; i<=n; i++) cin>>a[i].F>>a[i].S;

    sort(a + 1, a +n +1);

    vector<ll> dp(n+5);
    for(ll i = 1; i<=n; i++){
        dp[i] = max(dp[i-1] + a[i].S, a[i].F + a[i].S);
        ans = max(ans, dp[i] - a[i].F);
    }
    cout<<ans<<endl;



}




int main(){
    enter;

    ll T = 1;
    //cin>>T;

    while(T--){
        sdksjdksj();
    }

}

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