Submission #707288

#	Time	Username	Problem	Language	Result	Execution time	Memory
707288		MohammadAbduljalil	Art Exhibition (JOI18_art)	C++17	0 / 100	1 ms	212 KiB

art

#include <iostream>
#include <bits/stdc++.h>
typedef long long ll;

using namespace std;

int main()
{
     ll n;
     cin>>n;
     vector<pair<ll,ll>>art(n);
     vector<ll>prefix(n);

     for(int i=0;i<n;i++)
     {
         cin>>art[i].first;
         cin>>art[i].second;
     }

     sort(art.begin(),art.end());

     prefix[0]=art[0].second;
     for(int i=1;i<n;i++)
     {
         prefix[i]+=prefix[i-1]+art[i].second;
     }

     ll fm=0;
     ll maxx=-1e18;
     ll total=0;
     int idx=0;
     for(int i=0;i<n;i++)
     {   total+=art[i].second;
        if(total-art[i].first>=maxx)
           {
                maxx=total-art[i].first;
                 fm=art[i].first;
                 idx=i;
           }
     }

     ll mini=-1e18;
     total=0;

     for(int i=idx;i>=0;i--)
     {
        if(i-1>=0)
        total=prefix[idx]-prefix[i-1];
        else total=prefix[idx];

        if(total-fm+art[i].first>=mini)
        {
            mini=total-fm+art[i].first;
        }
     }

     ll trial2=-1e18;
     total=0;
     ll sm=0;
     int idx2=0;

     for(int i=0;i<n;i++)
     {
         if(i-1>=0)
        total=prefix[n-1]-prefix[i-1];
        else total=prefix[n-1];

        if(total+art[i].first>trial2)
        {
            trial2=total-art[i].first;
            sm=art[i].first;
            idx2=i;
        }
     }

     total=0;
     ll ans2=-1e18;
     for(int i=idx2;i<n;i++)
     {
         if(idx2-1>=0)
        total=prefix[i]-prefix[idx2-1];
        else total=prefix[i];

        if(total-art[i].first+sm>=ans2)
        {
            ans2=total-art[i].first+sm;
        }
     }

     total=0;
     ll ans3=-1e18;
     for(int i=0;i<n;i++)
     {
        if(i-1>=0)
        total=prefix[n-1]-prefix[i-1];
        else total=prefix[n-1];

        if(total-art[n-1].first+art[i].first>=ans3)
            ans3=total-art[n-1].first+art[i].first;

     }

    for(int i=0;i<n;i++)
     {
         if(art[i].second>mini)
         {
             mini=art[i].second;

         }
     }

     cout<<max({mini,ans2,ans3});
    return 0;
}

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