Submission #407175

#	Time	Username	Problem	Language	Result	Execution time	Memory
407175		victoriad	Art Exhibition (JOI18_art)	C++14	100 / 100	221 ms	32584 KiB

art

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
#include <utility>
#include <queue>
#include <map>
#include <iomanip>
#include <stack>
#include <fstream>
using namespace std;
 vector<pair<long long int,int> >dp;
 
void maximo(vector<pair<long long int,long long int> >&p,vector<long long int>&ps){
  long long m=0;
for(int k=0;k<(int)p.size();k++){
  dp[k].first=p[k].second;
  dp[k].second=k;
  for(int i=k-1;i>=0;i--){
  if(dp[k].first<(ps[k+1]-ps[dp[i].second]-(p[k].first-p[dp[i].second].first))){
      dp[k].first=ps[k+1]-ps[dp[i].second]-(p[k].first-p[dp[i].second].first);
      dp[k].second=dp[i].second;
    }
	else{
		break;
	}
  }
  m=max(m,dp[k].first);
  }
cout<<m;
}
  
 
int main(){
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n;
  cin>>n;
  vector<pair<long long int,long long int> >p(n);
  vector<long long int>ps(n+1);
  for(int i=0;i<n;i++){
    cin>>p[i].first>>p[i].second;
  }
  sort(p.begin(),p.end());
  dp.assign(n,make_pair(0,0));
  
  ps[0]=0;
   for(int i=1;i<n+1;i++){
     ps[i]=ps[i-1]+p[i-1].second;
   }
 maximo(p,ps);
 
  return 0;
}

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