Submission #843812

#	Time	Username	Problem	Language	Result	Execution time	Memory
843812		Iliya_	Art Exhibition (JOI18_art)	C++17	100 / 100	174 ms	35140 KiB

art

//IN THE NAME OF GOD
#include<bits/stdc++.h>
#pragma GCC optimize("O2,unroll-loops")
#define endl '\n'
#define F first
#define S second
using namespace std; 
typedef long long ll; 
typedef long double dll;

ll N = 5e5+7; 
vector<pair<ll,ll>> v, hav; 

int32_t main(){
     ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);  

     ll n; cin >> n; 
     for(ll i=1; i<=n; i++){
          ll a,b; cin >> a >> b; 
          v.push_back({a,b}); 
     }
     sort(v.begin(),v.end()); 
     hav.push_back(v[0]); 
     for(ll i=1; i<n; i++){
          if (v[i].F == hav.back().F) hav.back().S += v[i].S; 
          else hav.push_back(v[i]);
     }
     ll ans = 0, tmp = 0; 
     for(ll i=ll(hav.size())-1; i>=0; i--){
          ans = max(ans, hav[i].S);
          if (i == int(hav.size())-1) tmp = hav[i].S;
          else tmp = max(hav[i].S,tmp+hav[i].S-hav[i+1].F+hav[i].F); 
          ans = max(ans, tmp); 
     }
     cout << ans << endl; 

     return 0; 
}

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