oj.uz

답안 #660657

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
660657 2022-11-22T17:56:19 Z USER 로봇 (APIO13_robots) C++14
30 / 100
 1500 ms 37060 KB 
#include <bits/stdc++.h>
using namespace std;
 
typedef pair <int, int> pr;
int k, n, m, a[501][501][9][9];
char c[501][501];
 
const int inf = 1000000000;
pr go[4][501][501];
 
struct nod{
    int i, j;
    unsigned l, r;
 
    bool operator < (const nod& aux) const
    {
        return a[i][j][l][r] > a[aux.i][aux.j][aux.l][aux.r];
    }
};
 
priority_queue <nod> Q;
 
void afis(pr aux)
{
    cout << aux.first << ' ' << aux.second << '\n';
}
 
// 0 - Up, 1 - Left, 2 - Down, 3 - Right
 
int d1[] = { -1, 0, 1, 0 };
int d2[] = { 0, 1, 0, -1 };
 
inline bool in(int i, int j)
{
    return i >= 1 && i <= n && j >= 1 && j <= m;
}
 
inline void prev(int& dir)
{
    dir--;
    if (dir == -1)
        dir = 3;
}
 
inline void next(int& dir)
{
    dir++;
    if (dir == 4)
        dir = 0;
}
 
pr get(int dir, int i, int j)
{
    if (!in(i, j) || c[i][j] == 'x')
    {
        next(dir);
        next(dir);
        return { i + d1[dir], j + d2[dir] };
    }
 
    if (go[dir][i][j].first)
        return go[dir][i][j];
 
    int nxDir = dir;
 
    if (c[i][j] == 'A')
        prev(nxDir);
    else if (c[i][j] == 'C')
        next(nxDir);
 
    pr aux = get(nxDir, i + d1[nxDir], j + d2[nxDir]);
    go[dir][i][j] = aux;
    return aux;
}
 
inline bool digit(char c)
{
    return c >= '0' && c <= '9';
}
 
bool update(pr p, int val, int l, int r)
{
    if (a[p.first][p.second][l][r] > val)
    {
        a[p.first][p.second][l][r] = val;
        return 1;
    }
 
    return 0;
}
 
void lee()
{
    int l, r, i, j, x, y;
 
    while (!Q.empty())
    {
        i = Q.top().i;
        j = Q.top().j;
        l = Q.top().l;
        r = Q.top().r;
        Q.pop();
 
        for (int p = 0; p <= 3; p++)
        {
            x = go[p][i][j].first;
            y = go[p][i][j].second;
 
            if (update({ x, y }, a[i][j][l][r] + 1, l, r))
                Q.push({ x, y, unsigned(l), unsigned(r)});
        }
    }
}
 
int main()
{
  	ios::sync_with_stdio(false);
  	cin.tie(0);
    cin >> k >> m >> n;
 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            for (int l = 0; l < k; l++)
                for (int p = 0; p < k; p++)
                    a[i][j][l][p] = inf;
 
            cin >> c[i][j];
            if (isdigit(c[i][j]))
                c[i][j]--;
        }
 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            for (int l = 0; l <= 3; l++)
                get(l, i, j);
 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            if (digit(c[i][j]))
            {
                int aux = (c[i][j] - '0');
                update({ i, j }, 0, aux, aux);
                Q.push({ i, j, unsigned(aux), unsigned(aux) });
                lee();
            }
 
    for (int l = 2; l <= k; l++)
        for (int p = 0; p < k - l + 1; p++)
        {
            int q = p + l - 1;
            
            for (int i = 1; i <= n; i++)
                for (int j = 1; j <= m; j++)
                {
                    for (int t = p; t < q; t++)
                        update({ i, j }, a[i][j][p][t] + a[i][j][t + 1][q], p, q);
 
                    Q.push({ i, j, unsigned(p), unsigned(q)});
                }
 
            lee();
        }
 
    int mini = inf;
 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            mini = min(mini, a[i][j][0][k - 1]);
 
    if (mini == inf)
        cout << -1;
    else
        cout << mini;
 
    return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 0 ms 468 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct

Subtask #3
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 974 ms 36520 KB Output is correct
12 Correct 22 ms 34260 KB Output is correct
13 Correct 395 ms 37060 KB Output is correct
14 Execution timed out 1537 ms 36540 KB Time limit exceeded
15 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 468 KB Output is correct
5 Correct 0 ms 468 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 974 ms 36520 KB Output is correct
12 Correct 22 ms 34260 KB Output is correct
13 Correct 395 ms 37060 KB Output is correct
14 Execution timed out 1537 ms 36540 KB Time limit exceeded
15 Halted 0 ms 0 KB -