Submission #3882477
Source Code Expand
#include <queue> #include <vector> #include <iostream> using namespace std; int H, W, K; int input[50][50]; typedef pair<int, int> P; int dirx[] = {1, -1, 0, 0}, diry[] = {0, 0, 1, -1}; vector<P> solve() { bool used[H][W] = {}; vector<P> ans; for (;;) { int best_score = -1; vector<P> best_piece; for (int i = 0; i < H; i++) for (int j = 0; j < W; j++) { if (used[i][j] || input[i][j] == 0) continue; vector<P> v(K); priority_queue<pair<int, P> > pq; pq.push(make_pair(input[i][j], make_pair(i, j))); int count = 0; while (!pq.empty()) { int i0 = pq.top().second.first, j0 = pq.top().second.second; pq.pop(); if (used[i0][j0]) continue; v[count++] = make_pair(i0, j0); used[i0][j0] = true; if (count == K) break; for (int k = 0; k < 4; k++) { int i1 = i0 + diry[k], j1 = j0 + dirx[k]; if (0 <= i1 && i1 < H && 0 <= j1 && j1 < W && !used[i1][j1] && input[i1][j1] > 0) { pq.push(make_pair(input[i1][j1], make_pair(i1, j1))); } } } int score = 1; for (auto p : v) score *= input[p.first][p.second]; if (v.size() == count && score > best_score) { best_score = score; best_piece = v; } for (auto p : v) used[p.first][p.second] = false; } if (best_score > 0) { ans.insert(ans.end(), best_piece.begin(), best_piece.end()); for (auto p : best_piece) used[p.first][p.second] = true; // cerr << best_score << endl; } else break; } return ans; } int main() { cin >> H >> W >> K; for (int i = 0; i < H; i++) { string s; cin >> s; for (int j = 0; j < W; j++) input[i][j] = s[j]-'0'; } vector<P> v = solve(); cout << v.size() / K << endl; for (auto x : v) cout << x.first + 1 << ' ' << x.second + 1 << endl; }
Submission Info
Submission Time | |
---|---|
Task | A - Multiple Pieces |
User | kozima |
Language | C++14 (GCC 5.4.1) |
Score | 935948 |
Code Size | 2361 Byte |
Status | AC |
Exec Time | 312 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 | ||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 94012 / 1343058 | 88888 / 1343058 | 96380 / 1343058 | 89108 / 1343058 | 101734 / 1343058 | 90566 / 1343058 | 96321 / 1343058 | 86617 / 1343058 | 97596 / 1343058 | 94726 / 1343058 | ||||||||||||||||||||
Status |
|
|
|
|
|
|
|
|
|
|
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 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
subtask_01_01.txt | AC | 305 ms | 256 KB |
subtask_01_02.txt | AC | 299 ms | 256 KB |
subtask_01_03.txt | AC | 303 ms | 256 KB |
subtask_01_04.txt | AC | 310 ms | 256 KB |
subtask_01_05.txt | AC | 312 ms | 256 KB |
subtask_01_06.txt | AC | 302 ms | 256 KB |
subtask_01_07.txt | AC | 306 ms | 256 KB |
subtask_01_08.txt | AC | 303 ms | 256 KB |
subtask_01_09.txt | AC | 305 ms | 256 KB |
subtask_01_10.txt | AC | 298 ms | 256 KB |