Submission #157839

#	Time	Username	Problem	Language	Result	Execution time	Memory
157839		InfiniteJest	Art Exhibition (JOI18_art)	C++14	50 / 100	1059 ms	21116 KiB

art

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
#include <math.h>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
using namespace std;

ifstream in("input.txt");
ofstream out("output.txt");

typedef long long ll;

int n;
pair<ll,ll> v[500001];
ll pref[500001];
priority_queue<pair<ll,ll> > q;

int main(){
  cin>>n;
  for(int i=0;i<n;i++)cin>>v[i].fi>>v[i].se;
  sort(v,v+n);
  ll sum=0;
  int ind=0;
  ll mas=-1;
  for(int i=0;i<n;i++){
    sum+=v[i].se;
    pref[i]=sum;
    ll solp=sum-(v[i].fi-v[0].fi);
    if(solp>mas){
      mas=solp;
      ind=i;
    }
    q.push(mp(solp,i));
  }
  for(int i=1;i<n;i++){
    /*if(v[i].fi<=v[i-1].fi+v[i-1].se){
      //mas=max(mas,pref[ind]-pref[i-1]-(v[ind].fi-v[i].fi));
      continue;
    }
    for(int y=ind;y<n;y++){
      if(y<i)continue;
      ll solp=pref[y]-pref[i-1]-(v[y].fi-v[i].fi);
      if(solp>mas){
        mas=solp;
        ind=y;
      }
    }*/
    if(q.empty())break;
    while(!q.empty()&&q.top().se<i)q.pop();
    mas=max(mas,q.top().fi+v[i].fi-v[0].fi-pref[i-1]);
    //if(!q.empty())q.pop();
  }
  cout<<mas;

}

Compilation message (stderr)

art.cpp: In function 'int main()':
art.cpp:28:7: warning: variable 'ind' set but not used [-Wunused-but-set-variable]
   int ind=0;
       ^~~

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