제출 #157840

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
157840		InfiniteJest	Art Exhibition (JOI18_art)	C++14	100 / 100	373 ms	26840 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(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  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;

}

컴파일 시 표준 에러 (stderr) 메시지

art.cpp: In function 'int main()':
art.cpp:30: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: 50 / 50