Submission #1516205


Source Code Expand

#include <bits/stdc++.h>

using namespace std;

const int INF = 1145141919;

string c[305];
int cost[305][305][305], dp[305][305][305];

int main() {
	cin.tie(0);
	ios::sync_with_stdio(false);
	int H, W;
	cin >> H >> W;
	for (int i = 0; i < H; i++) {
		cin >> c[i];
	}

	for (int i = 0; i < W - 1; i++) {
		for (int j = 0; j <= H; j++) {
			for (int k = 0; k <= H; k++) {
				cost[i][j][k] = cost[i][max(j - 1, 0)][max(k - 1, 0)];
				if (j == 0 || k == 0) continue;
				cost[i][j][k] += (c[j - 1][i] == c[k - 1][i + 1]);
			}
		}
	}

	for (int i = 0; i < W - 1; i++) {
		for (int j = 0; j <= H; j++) {
			for (int k = 0; k <= H; k++) {
				dp[i][j][k] = INF;
			}
		}
	}
	for (int i = 0; i < W - 1; i++) dp[i][H][H] = 0;

	int ans = 0;
	for (int i = 0; i < W - 1; i++) {
		for (int j = H; j >= 0; j--) {
			for (int k = H; k >= 0; k--) {
				if (j > 0) dp[i][j - 1][k] = min(dp[i][j - 1][k], dp[i][j][k] + cost[i][j][k]);
				if (k > 0) dp[i][j][k - 1] = min(dp[i][j][k - 1], dp[i][j][k] + cost[i][j][k]);
			}
		}
		ans += dp[i][0][0];
	}
	cout << ans << endl;
	return 0;
}

Submission Info

Submission Time
Task D - Friction
User fine
Language C++14 (GCC 5.4.1)
Score 800
Code Size 1124 Byte
Status AC
Exec Time 246 ms
Memory 221568 KB

Judge Result

Set Name Sample Subtask All
Score / Max Score 0 / 0 300 / 300 500 / 500
Status
AC × 5
AC × 20
AC × 41
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 AC 1 ms 2304 KB
0_001.txt AC 1 ms 2304 KB
0_002.txt AC 1 ms 2304 KB
0_003.txt AC 1 ms 2304 KB
0_004.txt AC 2 ms 6528 KB
1_005.txt AC 1 ms 2304 KB
1_006.txt AC 3 ms 3072 KB
1_007.txt AC 3 ms 3072 KB
1_008.txt AC 3 ms 3072 KB
1_009.txt AC 3 ms 3072 KB
1_010.txt AC 3 ms 3072 KB
1_011.txt AC 3 ms 3072 KB
1_012.txt AC 3 ms 3072 KB
1_013.txt AC 2 ms 2688 KB
1_014.txt AC 3 ms 3072 KB
1_015.txt AC 2 ms 2816 KB
1_016.txt AC 3 ms 3072 KB
1_017.txt AC 1 ms 2432 KB
1_018.txt AC 3 ms 3072 KB
1_019.txt AC 2 ms 2816 KB
1_020.txt AC 3 ms 3072 KB
1_021.txt AC 3 ms 3072 KB
1_022.txt AC 3 ms 3072 KB
2_023.txt AC 42 ms 215296 KB
2_024.txt AC 246 ms 221568 KB
2_025.txt AC 246 ms 221568 KB
2_026.txt AC 245 ms 221568 KB
2_027.txt AC 246 ms 221568 KB
2_028.txt AC 246 ms 221568 KB
2_029.txt AC 50 ms 207616 KB
2_030.txt AC 246 ms 221568 KB
2_031.txt AC 41 ms 172800 KB
2_032.txt AC 246 ms 221568 KB
2_033.txt AC 80 ms 179584 KB
2_034.txt AC 246 ms 221568 KB
2_035.txt AC 142 ms 131328 KB
2_036.txt AC 246 ms 221568 KB
2_037.txt AC 11 ms 23936 KB
2_038.txt AC 246 ms 221568 KB
2_039.txt AC 13 ms 39808 KB
2_040.txt AC 246 ms 221568 KB