View Code of Problem 1052

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<queue>
#include<cstdlib>
#include<algorithm>
#include<stack>
#include<map>
#include<queue>
#include<vector>
using namespace std;
const int maxn = 1e4+10;
const int INF = 0x3f3f3f3f;
int p[maxn],t[maxn],dp[2][maxn][2],n,ans;
int main(){
 while(cin>>n){
    for(int i=1;i<=n;i++) cin>>p[i]>>t[i];
    for(int i=1;i<=n;i++) dp[0][i][0]=dp[0][i][1]=0;
    int x,nx=0;
    for(int i=1;i<n;i++){
        x=nx;nx^=1;
        for(int j=1;j<=n-i;j++){
            //0->left 1->right

            dp[nx][j][0]=min(dp[x][j+1][0]+p[j+1]-p[j],dp[x][j+1][1]+p[j+i]-p[j]);
            dp[nx][j][1]=min(dp[x][j][0]+p[j+i]-p[j],dp[x][j][1]+p[i+j]-p[i+j-1]);
            if(dp[nx][j][0]>=t[j]) dp[nx][j][0] = INF;
            if(dp[nx][j][1]>=t[i+j]) dp[nx][j][1] = INF;
        }
    }
    ans = min(dp[nx][1][0],dp[nx][1][1]);
    if(ans>=INF) cout<<"No solution\n";
    else cout<<ans<<"\n";

 }
    return 0;
}