CODE FESTIVAL 2016 qual C

Submission #949291

Source codeソースコード

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

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define pb push_back
#define fi first
#define se second

int h,w;
string c[300];

int cost[301][301];
int dp[301][301];
int dfs(int x, int y)
{
    if(dp[x][y]>=0) return dp[x][y];
    if(x+y==2*h) return 0;

    int ret=123456789;
    if(x<h) ret=min(ret,dfs(x+1,y)+cost[x][y]);
    if(y<h) ret=min(ret,dfs(x,y+1)+cost[x][y]);

    return dp[x][y]=ret;
}

int main()
{
    cin >>h >>w;
    rep(i,h) cin >>c[i];

    int ans=0;
    rep(i,w-1)
    {
        memset(cost,0,sizeof(cost));
        for(int a=h-1; a>=0; --a)for(int b=h-1; b>=0; --b) cost[a][b]=cost[a+1][b+1]+(c[h-1-a][i]==c[h-1-b][i+1]);
        memset(dp,-1,sizeof(dp));
        ans+=dfs(0,0);
    }
    printf("%d\n", ans);
    return 0;
}

Submission

Task問題 D - Friction
User nameユーザ名 imulan
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 800
Source lengthソースコード長 986 Byte
File nameファイル名
Exec time実行時間 306 ms
Memory usageメモリ使用量 1152 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - 0_000.txt,0_001.txt,0_002.txt,0_003.txt,0_004.txt
Subtask 300 / 300 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 500 / 500 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

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
0_000.txt AC 3 ms 896 KB
0_001.txt AC 3 ms 896 KB
0_002.txt AC 3 ms 896 KB
0_003.txt AC 3 ms 896 KB
0_004.txt AC 3 ms 896 KB
1_005.txt AC 3 ms 896 KB
1_006.txt AC 5 ms 1024 KB
1_007.txt AC 5 ms 1024 KB
1_008.txt AC 5 ms 1024 KB
1_009.txt AC 5 ms 1024 KB
1_010.txt AC 5 ms 1024 KB
1_011.txt AC 5 ms 1024 KB
1_012.txt AC 5 ms 1024 KB
1_013.txt AC 4 ms 1024 KB
1_014.txt AC 5 ms 1024 KB
1_015.txt AC 4 ms 1024 KB
1_016.txt AC 5 ms 1024 KB
1_017.txt AC 3 ms 896 KB
1_018.txt AC 5 ms 1024 KB
1_019.txt AC 4 ms 1024 KB
1_020.txt AC 5 ms 1024 KB
1_021.txt AC 5 ms 1024 KB
1_022.txt AC 5 ms 1024 KB
2_023.txt AC 14 ms 896 KB
2_024.txt AC 305 ms 1152 KB
2_025.txt AC 306 ms 1152 KB
2_026.txt AC 305 ms 1152 KB
2_027.txt AC 306 ms 1152 KB
2_028.txt AC 306 ms 1152 KB
2_029.txt AC 23 ms 1024 KB
2_030.txt AC 305 ms 1152 KB
2_031.txt AC 20 ms 1024 KB
2_032.txt AC 306 ms 1152 KB
2_033.txt AC 75 ms 1152 KB
2_034.txt AC 305 ms 1152 KB
2_035.txt AC 176 ms 1024 KB
2_036.txt AC 306 ms 1152 KB
2_037.txt AC 11 ms 1024 KB
2_038.txt AC 305 ms 1152 KB
2_039.txt AC 10 ms 1024 KB
2_040.txt AC 305 ms 1152 KB