Submission #1177342


Source Code Expand

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,int> plli;
typedef pair<int,pii> pipii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vi> vvi;
typedef vector<vvi> vvvi;
typedef vector<pii> vpii;

#define rep(i,n) for (int i=0;i<(n);i++)
#define rep2(i,a,b) for (int i=(a);i<(b);i++)
#define rrep(i,n) for (int i=(n);i>=0;i--)
#define rrep2(i,a,b) for (int i=(a);i>b;i--)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define all(a) (a).begin(),(a).end()

const int mod = 1e9 + 7;
const ll INF = 1<<30;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int n;
int l[405],r[405];
vvvi dp(405,vvi(405,vi(405,1e9)));

int main(){
    cin >> n;
    if (n>400) return 0;
    rep(i,n) cin >> l[i] >> r[i];
    rep2(j,1,401){
        int w=r[0]-l[0];
        if (j+w>400) break;
        dp[1][j][j+w]=abs(l[0]-j);
    }
    rep2(i,1,n)rep(j,401)rep(k,401){
        int w=r[i]-l[i];
        if (k<l[i]){
            dp[i+1][k][k+w]=min(dp[i+1][k][k+w],dp[i][j][k]+l[i]-k);
        }
        else if (r[i]<j){
            dp[i+1][j-w][j]=min(dp[i+1][j-w][j],dp[i][j][k]+j-r[i]);
        }
        else{
            dp[i+1][j][k]=min(dp[i+1][j][k],dp[i][j][k]);
        }
    }
    int ans=INF;
    int w=r[n-1]-l[n-1];
    rep(j,400){
        if (j+w>400) break;
        ans=min(ans,dp[n][j][j+w]);
    }
    cout << ans << endl;
    return 0;
}

Submission Info

Submission Time
Task E - NarrowRectangles
User roto_37
Language C++14 (GCC 5.4.1)
Score 0
Code Size 1525 Byte
Status RE
Exec Time 338 ms
Memory 266112 KB

Judge Result

Set Name Sample Subtask All
Score / Max Score 0 / 0 0 / 300 0 / 700
Status
MLE × 4
RE × 1
MLE × 13
MLE × 36
RE × 1
Set Name Test Cases
Sample 0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt, 0_004.txt
Subtask 0_000, 0_001, 0_004, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt
All 0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt, 0_004.txt, 1_005.txt, 1_006.txt, 1_007.txt, 1_008.txt, 1_009.txt, 1_010.txt, 1_011.txt, 1_012.txt, 1_013.txt, 1_014.txt, 1_015.txt, 1_016.txt, 1_017.txt, 2_018.txt, 2_019.txt, 2_020.txt, 2_021.txt, 2_022.txt, 2_023.txt, 2_024.txt, 2_025.txt, 2_026.txt, 2_027.txt, 2_028.txt, 2_029.txt, 2_030.txt, 2_031.txt, 2_032.txt, 2_033.txt, 2_034.txt, 2_035.txt, 2_036.txt
Case Name Status Exec Time Memory
0_000.txt MLE 132 ms 266112 KB
0_001.txt MLE 133 ms 266112 KB
0_002.txt MLE 133 ms 266112 KB
0_003.txt RE 215 ms 266112 KB
0_004.txt MLE 131 ms 266112 KB
1_005.txt MLE 338 ms 266112 KB
1_006.txt MLE 338 ms 266112 KB
1_007.txt MLE 284 ms 266112 KB
1_008.txt MLE 314 ms 266112 KB
1_009.txt MLE 314 ms 266112 KB
1_010.txt MLE 313 ms 266112 KB
1_011.txt MLE 314 ms 266112 KB
1_012.txt MLE 314 ms 266112 KB
1_013.txt MLE 313 ms 266112 KB
1_014.txt MLE 312 ms 266112 KB
1_015.txt MLE 314 ms 266112 KB
1_016.txt MLE 312 ms 266112 KB
1_017.txt MLE 312 ms 266112 KB
2_018.txt MLE 132 ms 266112 KB
2_019.txt MLE 131 ms 266112 KB
2_020.txt MLE 131 ms 266112 KB
2_021.txt MLE 131 ms 266112 KB
2_022.txt MLE 131 ms 266112 KB
2_023.txt MLE 132 ms 266112 KB
2_024.txt MLE 132 ms 266112 KB
2_025.txt MLE 132 ms 266112 KB
2_026.txt MLE 131 ms 266112 KB
2_027.txt MLE 132 ms 266112 KB
2_028.txt MLE 131 ms 266112 KB
2_029.txt MLE 131 ms 266112 KB
2_030.txt MLE 131 ms 266112 KB
2_031.txt MLE 131 ms 266112 KB
2_032.txt MLE 132 ms 266112 KB
2_033.txt MLE 131 ms 266112 KB
2_034.txt MLE 131 ms 266112 KB
2_035.txt MLE 131 ms 266112 KB
2_036.txt MLE 134 ms 266112 KB