Submission #1186358


Source Code Expand

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
#include<cmath>
using namespace std;
int H, W, K, T, a[450], b[450], c[450], d[450], I[31][31], dx[4] = { -1,0,1,0 }, dy[4] = { 0,1,0,-1 };
char Y[5] = "URDL"; bool used[31][31];
int score() {
	int ret = 0;
	for (int i = 1; i <= K; i++)ret += abs(a[i] - c[i]) + abs(b[i] - d[i]);
	return ret + 20;
}
int dist(int a1, int a2, int a3, int a4) { return abs(a1 - a3) + abs(a2 - a4); }
int main() {
	cin >> H >> W >> K >> T;
	for (int i = 1; i <= K; i++) { cin >> a[i] >> b[i] >> c[i] >> d[i]; I[a[i]][b[i]] = i; }
	int maxn = 0, maxid = score(); vector<string>V;
	for (int i = 1; i <= T; i++) {
		string O = ""; for (int j = 0; j < K; j++)O += " ";
		for (int j = 1; j <= H; j++) { for (int k = 1; k <= W; k++)used[j][k] = false; }
		for (int j = 1; j <= H; j++) {
			for (int k = 1; k <= W; k++) {
				if (I[j][k] == 0 || O[I[j][k] - 1] != ' ')continue;
				bool OK = true;
				for (int l = 0; l < 4; l++) {
					int cx = j + dx[l], cy = k + dy[l], num = I[j][k];
					if (cx <= 0 || cy <= 0 || cx > H || cy > W || I[cx][cy] >= 1 || used[cx][cy] == true)continue;
					if (dist(cx, cy, c[I[j][k]], d[num]) > dist(j, k, c[num], d[num]))continue;
					O[num - 1] = Y[l]; a[num] = cx; b[num] = cy; swap(I[cx][cy], I[j][k]); used[j][k] = true;
					OK = false; break;
				}
				if (OK == true)O[I[j][k] - 1] = '-';
			}
		}
		V.push_back(O);
		int score2 = 1000000000 / ((score())*(1000 + i));
		if (maxn < score2) { maxn = score2; maxid = i; }
	}
	cout << maxid << endl;
	for (int i = 0; i < maxid; i++) { cout << V[i] << endl; }
	return 0;
}

Submission Info

Submission Time
Task B - 日本橋大渋滞
User E869120
Language C++14 (GCC 5.4.1)
Score 4366
Code Size 1651 Byte
Status AC
Exec Time 9 ms
Memory 256 KB

Judge Result

Set Name test_01 test_02 test_03 test_04 test_05 test_06 test_07 test_08 test_09 test_10 test_11 test_12 test_13 test_14 test_15 test_16 test_17 test_18 test_19 test_20 test_21 test_22 test_23 test_24 test_25 test_26 test_27 test_28 test_29 test_30
Score / Max Score 147 / 50000 157 / 50000 133 / 50000 160 / 50000 171 / 50000 152 / 50000 152 / 50000 124 / 50000 123 / 50000 142 / 50000 147 / 50000 150 / 50000 135 / 50000 141 / 50000 116 / 50000 157 / 50000 150 / 50000 147 / 50000 154 / 50000 151 / 50000 135 / 50000 149 / 50000 147 / 50000 144 / 50000 144 / 50000 154 / 50000 155 / 50000 138 / 50000 147 / 50000 144 / 50000
Status
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
AC × 1
Set Name Test Cases
test_01 subtask_01_01.txt
test_02 subtask_01_02.txt
test_03 subtask_01_03.txt
test_04 subtask_01_04.txt
test_05 subtask_01_05.txt
test_06 subtask_01_06.txt
test_07 subtask_01_07.txt
test_08 subtask_01_08.txt
test_09 subtask_01_09.txt
test_10 subtask_01_10.txt
test_11 subtask_01_11.txt
test_12 subtask_01_12.txt
test_13 subtask_01_13.txt
test_14 subtask_01_14.txt
test_15 subtask_01_15.txt
test_16 subtask_01_16.txt
test_17 subtask_01_17.txt
test_18 subtask_01_18.txt
test_19 subtask_01_19.txt
test_20 subtask_01_20.txt
test_21 subtask_01_21.txt
test_22 subtask_01_22.txt
test_23 subtask_01_23.txt
test_24 subtask_01_24.txt
test_25 subtask_01_25.txt
test_26 subtask_01_26.txt
test_27 subtask_01_27.txt
test_28 subtask_01_28.txt
test_29 subtask_01_29.txt
test_30 subtask_01_30.txt
Case Name Status Exec Time Memory
subtask_01_01.txt AC 2 ms 256 KB
subtask_01_02.txt AC 2 ms 256 KB
subtask_01_03.txt AC 2 ms 256 KB
subtask_01_04.txt AC 2 ms 256 KB
subtask_01_05.txt AC 2 ms 256 KB
subtask_01_06.txt AC 2 ms 256 KB
subtask_01_07.txt AC 2 ms 256 KB
subtask_01_08.txt AC 2 ms 256 KB
subtask_01_09.txt AC 2 ms 256 KB
subtask_01_10.txt AC 2 ms 256 KB
subtask_01_11.txt AC 2 ms 256 KB
subtask_01_12.txt AC 2 ms 256 KB
subtask_01_13.txt AC 2 ms 256 KB
subtask_01_14.txt AC 2 ms 256 KB
subtask_01_15.txt AC 2 ms 256 KB
subtask_01_16.txt AC 2 ms 256 KB
subtask_01_17.txt AC 9 ms 256 KB
subtask_01_18.txt AC 2 ms 256 KB
subtask_01_19.txt AC 2 ms 256 KB
subtask_01_20.txt AC 2 ms 256 KB
subtask_01_21.txt AC 2 ms 256 KB
subtask_01_22.txt AC 2 ms 256 KB
subtask_01_23.txt AC 2 ms 256 KB
subtask_01_24.txt AC 2 ms 256 KB
subtask_01_25.txt AC 2 ms 256 KB
subtask_01_26.txt AC 2 ms 256 KB
subtask_01_27.txt AC 2 ms 256 KB
subtask_01_28.txt AC 2 ms 256 KB
subtask_01_29.txt AC 2 ms 256 KB
subtask_01_30.txt AC 2 ms 256 KB