oj.uz

Submission #157830

# Submission time Handle Problem Language Result Execution time Memory
157830 2019-10-13T09:26:34 Z InfiniteJest Art Exhibition (JOI18_art) C++14
0 / 100
 2 ms 380 KB 
#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

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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 380 KB Output isn't correct
2 Halted 0 ms 0 KB -