?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
1037305 |
Contestant: goo.gl_SsAhv |
142C - 11 | GNU C++ | Accepted | 440 ms | 64704 KB | 2012-01-12 20:25:19 | 2012-01-12 21:47:32 |
#define _CRT_SECURE_NO_DEPRECATE #include <stdio.h> #include <vector> #include <algorithm> #include <stdlib.h> #include <ctime> #include <set> #include <map> #include <queue> #include <string> #include <math.h> #include <queue> #include <memory.h> #include <iostream> #include <stack> #include <complex> #include <list> using namespace std; void ASS(bool b) { if (!b) { ++*(int*)0; } } #define FOR(i, x) for (int i = 0; i < (int)(x); i++) #define CL(x) memset(x, 0, sizeof(x)) #define CLX(x, y) memset(x, y, sizeof(x)) #pragma comment(linker, "/STACK:106777216") typedef vector<int> vi; typedef long long LL; int m; struct edge { int x, cost; int msk; }; int dd[3][4] = {{7, 4, 2, 1}, {2, 7, 2, 7}, {2, 4, 7, 1}}; vector<edge> g[1 << 18]; int III; void rec(int x, int a0, int a1, int a2, int cnt, int msk) { if (x + 3 > m) { edge e; e.x = (a2 << m) + a1; e.cost = cnt; e.msk = msk; g[III].push_back(e); return; } rec(x + 1, a0, a1, a2, cnt, msk * 5); FOR(i, 4) { if ((a0 & (dd[0][i] << x)) == 0 && (a1 & (dd[1][i] << x)) == 0 && (a2 & (dd[2][i] << x)) == 0) { rec(x + 1, a0 | (dd[0][i] << x), a1 | (dd[1][i] << x), a2 | (dd[2][i] << x), cnt + 1, msk * 5 + i + 1); } } } int d[10][1 << 18]; int dmsk[10][1 << 18]; int p[10][1 << 18]; char ans[16][16]; int main() { int n; cin >> n >> m; if (n < 3 || m < 3) { printf("0\n"); FOR(i, n) { FOR(j, m) { printf("."); } printf("\n"); } return 0; } FOR(i, 1 << (m * 2)) { III = i; rec(0, i & ((1 << m) - 1), i >> m, 0, 0, 0); } CLX(p, 0xFF); const int inf = 1 << 20; FOR(i, 10) FOR(j, (1 << (2 * m))) d[i][j] = -inf; d[0][0] = 0; FOR(z, n - 2) { FOR(i, (1 << (2 * m))) if (d[z][i] != -inf) { FOR(j, g[i].size()) { const edge& e = g[i][j]; if (d[z + 1][e.x] < d[z][i] + e.cost) { d[z + 1][e.x] = d[z][i] + e.cost; dmsk[z + 1][e.x] = e.msk; p[z + 1][e.x] = i; } } } } int best = 0; int bestPos = 0; FOR(i, (1 << (2 * m))) { if (best < d[n - 2][i]) { best = d[n - 2][i]; bestPos = i; } } char cur = 'A'; CLX(ans, '.'); for (int z = n - 2; z >= 1; z --) { int msk = dmsk[z][bestPos]; for (int i = m - 3; i >= 0; i--) { int idx = msk % 5; if (idx) { idx--; FOR(x, 3) FOR(y, 3) { if ((dd[x][idx] >> y) & 1) ans[z - 1 + x][i + y] = cur; } cur++; } msk /= 5; } bestPos = p[z][bestPos]; } cout << best << endl; FOR(i, n) { FOR(j, m) cout << ans[i][j]; cout << endl; } return 0; }
?
?
?
?