Submission #157825

#	Time	Username	Problem	Language	Result	Execution time	Memory
157825		InfiniteJest	Art Exhibition (JOI18_art)	C++14	0 / 100	2 ms	376 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];

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;
    }
  }
  for(int i=1;i<=ind;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;
      }
    }
  }
  cout<<mas;

}

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