Submission #707291

#	Time	Username	Problem	Language	Result	Execution time	Memory
707291		Mohamed_Kachef06	Art Exhibition (JOI18_art)	C++17	0 / 100	0 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+10);
     vector<ll>prefix(n+10);
 
     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