Submission #262233

#TimeUsernameProblemLanguageResultExecution timeMemory
262233iliccmarkoArt Exhibition (JOI18_art)C++14
100 / 100
288 ms20984 KiB
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl "\n"
const int N = 5e5 + 5;
typedef struct struc{
ll a, b;
}art;
art arr[N];
int n;


bool cmp(art x, art y)
{
    return x.a<y.a;
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //freopen("sample-02-in.txt","r",stdin);
    cin>>n;
    for(int i = 1;i<=n;i++)
    {
        cin>>arr[i].a>>arr[i].b;
    }
    sort(arr+1, arr+n+1, cmp);
    ll maks = 0;
    ll ans = 0;
    int poz = 1;
    ll pret = arr[1].a;
    for(int i = 2;i<=n;i++)
    {
        if(arr[i].a==pret)
        {
            arr[poz].b += arr[i].b;
        }
        else
        {
            pret = arr[i].a;
            poz++;
            arr[poz].a = arr[i].a;
            arr[poz].b = arr[i].b;
        }
    }
 /*   for(int i = 1;i<=poz;i++)
        cout<<arr[i].a<<" "<<arr[i].b<<endl; */
    for(int i = 1;i<=poz;i++)
    {
        if(i==1)
        {
            ans = arr[1].b;
            maks = arr[1].b + arr[1].a;
        }
        else
        {
            ans = max(ans, maks - arr[i].a + arr[i].b);
            ans = max(ans, arr[i].b);
            maks = max(maks + arr[i].b, arr[i].b + arr[i].a);
        }
    }
    cout<<ans;



    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...