Submission #262233

#	Time	Username	Problem	Language	Result	Execution time	Memory
262233		iliccmarko	Art Exhibition (JOI18_art)	C++14	100 / 100	288 ms	20984 KiB

art

#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;
}

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