Submission #1087370

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pdd pair<double,double>
#define X first
#define Y second
#define REP(i,a) for(int i=0;i<a;++i)
#define REPP(i,a,b) for(int i=a;i<b;++i)
#define FILL(a,x) memset(a,x,sizeof(a))
#define foreach( gg,itit )  for( typeof(gg.begin()) itit=gg.begin();itit!=gg.end();itit++ )
#define mp make_pair
#define pb push_back
#define all(s) s.begin(),s.end()
#define present(c,x) ((c).find(x) != (c).end())
const double EPS = 1e-8;
const int mod = 1e9+7;
const int N = 1e6+10;
const ll INF = 1e18;

//#define DEBUG
ll power(ll x,ll y){
  ll t=1;
  while(y>0){
    if(y%2) y-=1,t=t*x%mod;
    else y/=2,x=x*x%mod;
  }
  return t;
}
#ifdef DEBUG
#define dprintf(fmt,...) fprintf(stderr,fmt,__VA_ARGS__)
#else
#define dprintf(fmt,...)
#endif

vector<pii> arr;
int cmp(pii a,pii b){
  return a.Y-a.X<b.Y-b.X;
}
ll dp[5005][5005];
int main(){
  int n; scanf("%d",&n); 
  if(n==1){
    printf("0\n"); exit(0);
  }
  REP(i,n){
    pii z; scanf("%d%d",&z.X,&z.Y); z.X=-z.X; arr.pb(z);
  }
  sort(all(arr),cmp);
  reverse(all(arr));
  int fl=1;
  REP(i,n-1) if(arr[i].X-arr[i].Y!=arr[i+1].X-arr[i+1].Y) fl=0;
  if(fl){
    sort(all(arr));
    swap(arr[n/2],arr[n-1]);
  } 
  REP(i,n+1) REP(j,n+1)  dp[i][j]=INF;
  dp[0][0]=0;
  ll lk = -arr[n-1].X,rk=arr[n-1].Y;
  ll ans=INF;
  REP(i,n){
    ll ls = arr[i].X,rs=arr[i].Y;
    ll dis = rs-ls;
    
   // printf("%lld %lld\n",lk,rk);
    REP(j,i+1)if(dp[i][j]<INF){
    //  printf("%d %d %lld\n",i,j,dp[i][j]);
      dp[i+1][j]=min(dp[i+1][j],dp[i][j]+(i-j)*dis+lk+rs);
      dp[i+1][j+1]=min(dp[i+1][j+1],dp[i][j]+j*dis+rk-ls);
    }
  }
  REP(i,n) ans=min(ans,dp[n-1][i]);
  printf("%lld\n",ans);
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:43:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   int n; scanf("%d",&n); 
                        ^
./Main.cpp:48:35: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     pii z; scanf("%d%d",&z.X,&z.Y); z.X=-z.X; arr.pb(z);
                                   ^

Judge Result