Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

 
 
 
 
General
 
 
# 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
→ Source
#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;
}
?
Time: ? ms, memory: ? KB
Verdict: ?
Input
?
Participant's output
?
Jury's answer
?
Checker comment
?
Diagnostics
?
Click to see test details