Submission #1814737


Source Code Expand

#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<iostream>
#include<string>
#include<stack>
#include<queue>
#include<vector>
#include<map>
#include<set>
#include<algorithm>
#include<numeric>

#define rep(n) for(int i=0;i<n;i++)
#define repp(j, n) for(int j=0;j<n;j++)
#define reppp(i, m, n) for(int i=m;i<=n;i++)
#define all(c) c.begin(), c.end()
#define rall(c) c.rbegin(), c.rend()
#define pb(x) push_back(x)
#define eb(x,y) emplace_back(x,y)
#define MOD 1000000007
#define MAX 1000000001
#define INF 1410065408
#define EPS 1e-9
#define DEBUG 0
#define ll long long
#define Pll pair<ll, ll>
#define Pii pair<int, int>
 
using namespace std;

signed main(){
    int H, W;
    cin >> H >> W;

    vector<string> c(H);
    rep(H) cin >> c[i];
    
    int ans = 0;
    vector< vector<int> > dp(H+1, vector<int>(H+1));
    repp(k, W-1){
        repp(i, H+1) repp(j, H+1) dp[i][j] = INF;
        dp[0][0] = 0;

        repp(i, H+1){
            repp(j, H+1){
                if(i == H && j == H) break;
                int cost = 0;
                int ii = i, jj = j;
                int base = min(i, j);
                while(ii < H && jj < H){
                    if(c[jj-base][k] == c[ii-base][k+1]){
                        cost++;
                    }
                    ii++;
                    jj++;
                }
                
                // cout << i << " " << j << " " << dp[i][j] << endl;
                if(i < H) dp[i+1][j] = min(dp[i+1][j], dp[i][j] + cost);
                if(j < H) dp[i][j+1] = min(dp[i][j+1], dp[i][j] + cost);
            }
        }
        cout << dp[H][H] << endl;
        ans += dp[H][H];
    }
    cout << ans;
}

Submission Info

Submission Time
Task D - Friction
User Noimin
Language C++14 (Clang 3.8.0)
Score 0
Code Size 1746 Byte
Status WA
Exec Time 2103 ms
Memory 768 KB

Judge Result

Set Name Sample Subtask All
Score / Max Score 0 / 0 0 / 300 0 / 500
Status
WA × 5
WA × 20
WA × 29
TLE × 12
Set Name Test Cases
Sample 0_000.txt, 0_001.txt, 0_002.txt, 0_003.txt, 0_004.txt
Subtask 0_000.txt, 0_001.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, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_022.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, 1_018.txt, 1_019.txt, 1_020.txt, 1_021.txt, 1_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, 2_037.txt, 2_038.txt, 2_039.txt, 2_040.txt
Case Name Status Exec Time Memory
0_000.txt WA 1 ms 256 KB
0_001.txt WA 1 ms 256 KB
0_002.txt WA 1 ms 256 KB
0_003.txt WA 1 ms 256 KB
0_004.txt WA 1 ms 256 KB
1_005.txt WA 1 ms 256 KB
1_006.txt WA 50 ms 640 KB
1_007.txt WA 50 ms 640 KB
1_008.txt WA 50 ms 640 KB
1_009.txt WA 50 ms 640 KB
1_010.txt WA 50 ms 640 KB
1_011.txt WA 43 ms 640 KB
1_012.txt WA 50 ms 640 KB
1_013.txt WA 12 ms 384 KB
1_014.txt WA 50 ms 640 KB
1_015.txt WA 18 ms 384 KB
1_016.txt WA 50 ms 640 KB
1_017.txt WA 1 ms 256 KB
1_018.txt WA 50 ms 640 KB
1_019.txt WA 13 ms 384 KB
1_020.txt WA 50 ms 640 KB
1_021.txt WA 46 ms 640 KB
1_022.txt WA 50 ms 640 KB
2_023.txt WA 2 ms 256 KB
2_024.txt TLE 2103 ms 768 KB
2_025.txt TLE 2103 ms 768 KB
2_026.txt TLE 2103 ms 768 KB
2_027.txt TLE 2103 ms 768 KB
2_028.txt TLE 2103 ms 768 KB
2_029.txt WA 53 ms 256 KB
2_030.txt TLE 2103 ms 768 KB
2_031.txt WA 42 ms 256 KB
2_032.txt TLE 2103 ms 768 KB
2_033.txt WA 756 ms 384 KB
2_034.txt TLE 2103 ms 768 KB
2_035.txt TLE 2103 ms 640 KB
2_036.txt TLE 2103 ms 768 KB
2_037.txt WA 81 ms 384 KB
2_038.txt TLE 2103 ms 768 KB
2_039.txt WA 37 ms 256 KB
2_040.txt TLE 2103 ms 768 KB