Submission #753858

#	Time	Username	Problem	Language	Result	Execution time	Memory
753858		emad234	Art Exhibition (JOI18_art)	C++17	100 / 100	237 ms	32752 KiB

art

#include <bits/stdc++.h>
#define all(v) ((v).begin(),(v).end())
#define ll long long
using namespace std;
const ll mod = 1e9 + 7;
const ll mxN = 2e6 + 1;
pair<ll,ll>a[mxN];
vector<pair<ll,ll>>v;
ll prfx[mxN];
signed main()
{
  ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  ll n;
  cin >>n;
  for(ll i = 0;i < n;i++) cin >>a[i].first>>a[i].second;
  ll ans = 0;
  sort(a,a + n);
  ll bf = -1;
  ll sum2 = 0;
  for(ll i = 0;i < n;i++){
    if(a[i].first != bf && bf != -1){
      v.push_back({bf,sum2});
      sum2 = 0;
    }
    sum2 += a[i].second;
    bf = a[i].first;
  }
  v.push_back({bf,sum2});
  // cout<<'\n';
  // for(auto x : v) cout<<x.first<<' '<<x.second<<'\n';
  prfx[0] = v[0].second;
  for(ll i = 1;i < n;i++){
    prfx[i] = prfx[i - 1] + v[i].second;
  }
  ll l = 0;
  ans = v[0].second;
  // cout<<ans<<'\n';
  for(ll i = 1;i < v.size();i++){
    ll x = 0;
    if(l != 0) x = prfx[l - 1];
    ll sum = prfx[i] - x - v[i].first + v[l].first;
    ll sum1 = v[i].second;
    if(sum1 >= sum){
      l = i;
    }
    ans = max(max(ans,sum),sum1);
  }
  cout<<ans<<'\n';
}

Compilation message (stderr)

art.cpp: In function 'int main()':
art.cpp:38:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |   for(ll i = 1;i < v.size();i++){
      |                ~~^~~~~~~~~~

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