제출 #702270

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
702270		NourWael	Art Exhibition (JOI18_art)	C++14	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;
        }
     }

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

         }
     }


     cout<<mini;
    return 0;
}

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