Submission #707317

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

art

#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 >> 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, mx = -1e18, total = 0, idx = 0;
     for (int i = 0; i < n; i++) {
         total += art[i].second;
         if (total - art[i].first >= mx) {
             mx = 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, sm = 0, idx2 = 0;
     total = 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