oj.uz

Submission #968240

# Submission time Handle Problem Language Result Execution time Memory
968240 2024-04-23T08:39:02 Z ShauryaTheShep Robots (APIO13_robots) C++14
100 / 100
 1104 ms 102864 KB 
#include <bits/stdc++.h>
#define max 500
#define maxn 505
#define sm 9
#define maxlog 20
#define INF 1000000010
#define mod 998244353
#define LINF 1000000000000000005
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cout << "passed"<<endl;
//#pragma GCC optimize("O3" , "Ofast" , "unroll-loops" , "fast-math")
//#pragma GCC target("avx2")
 
using namespace std;
 
char c[maxn][maxn];
int dp[maxn][maxn][sm][sm];
int state[maxn][maxn][4];
pair<int, int> stops[maxn][maxn][4];
 
int n, h, w;
 
void read() {
    cin >> n >> w >> h;
    h += 2;w += 2;
    for (int i = 0; i < w; ++i)
        c[0][i] = c[h - 1][i] = 'x';
    for (int i = 0; i < h; ++i)
        c[i][0] = c[i][w - 1] = 'x';
    for (int i = 1; i < h - 1; ++i)
        for (int j = 1; j < w - 1; ++j)
            cin >> c[i][j];
    for (int i = 0; i < h; ++i)
        for (int j = 0; j < w; ++j)
            for (int k = 0; k < n; ++k)
                for (int l = 0; l < n; ++l)
                    dp[i][j][k][l] = INF;
}
 
int dirx[] = {0, 1, 0, -1};
int diry[] = {1, 0, -1, 0};
 
 
pair<int, int> dfs(int i, int j, int k) {
    if (state[i][j][k] == 2)
        return stops[i][j][k];
    if (state[i][j][k] == 1)
        return stops[i][j][k] = {i, j};
    state[i][j][k] = 1;
    int nk = k;
    if (c[i][j] == 'A')
        nk = (k + 3) % 4;
    if (c[i][j] == 'C')
        nk = (k + 1) % 4;
    
	int ni = i + dirx[nk], nj = j + diry[nk];
    
	if (c[ni][nj] == 'x') {
        state[i][j][k] = 2;
        return stops[i][j][k] = {i, j};
    }
    else {
        stops[i][j][k] = dfs(ni, nj, nk);
        if (state[ni][nj][nk] == 1)
            stops[i][j][k] = {i, j};
        else
            state[i][j][k] = 2;
        return stops[i][j][k];
    }
}
 
 
void solve() {
    for (int len = 0; len < n; ++len) {
        for (int l = 0; l + len < n; ++l) {
            const int r = l + len;
            vector<vector<pair<int, int>>> v(maxn * maxn + 5);
            if (len == 0) {
                for (int i = 0; i < h; ++i)
                    for (int j = 0; j < w; ++j)
                        if (c[i][j] - '1' == l) {
                            dp[i][j][l][r] = 0;
                            v[0].push_back({i, j});
                        }
            }
            else {
                for (int i = 0; i < h; ++i)
                    for (int j = 0; j < w; ++j) {
                        int minn = INF;
                        for (int k = l; k < r; ++k)
                            minn = min(minn, dp[i][j][l][k] + dp[i][j][k + 1][r]);
                        dp[i][j][l][r] = minn;
                        if (minn < maxn * maxn)
                            v[minn].push_back({i, j});
                    }
			}
            for (int d = 0; d < maxn * maxn; ++d)
                for (pair <int, int> e : v[d])
                    for (int k = 0; k < 4; ++k) {
                        pair <int, int> nb = dfs(e.X, e.Y, k);
                        if (dp[nb.X][nb.Y][l][r] > d + 1) {
                            dp[nb.X][nb.Y][l][r] = d + 1;
                            v[d + 1].push_back({nb.X, nb.Y});
                        }
                    }
//            if (l == 0 and r == 1) {
//	        	cout << "c : " << l << " " << r << " " << dp[4][4][0][1] << "\n";
//	        	exit(0);
//			}   
        }
    }
}
 
void print() {
    int ans = INF;
    for (int i = 0; i < h; ++i)
        for (int j = 0; j < w; ++j)
            ans = min(ans, dp[i][j][0][n - 1]);
    if(ans == INF)
        cout << -1 << endl;
    else
        cout << ans << endl;
}
 
int main() {
//	freopen ("input.txt", "r",stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
//    cout << (int)'x' << " " << (int)'1';
//    return 0;
    read();
    solve();
    print();
    return 0;
}

Compilation message

robots.cpp: In function 'std::pair<int, int> dfs(int, int, int)':
robots.cpp:56:5: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   56 |     if (c[i][j] == 'C')
      |     ^~
robots.cpp:59:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   59 |  int ni = i + dirx[nk], nj = j + diry[nk];
      |  ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8448 KB Output is correct
2 Correct 5 ms 8448 KB Output is correct
3 Correct 5 ms 8448 KB Output is correct
4 Correct 5 ms 10588 KB Output is correct
5 Correct 5 ms 10588 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8448 KB Output is correct
2 Correct 5 ms 8448 KB Output is correct
3 Correct 5 ms 8448 KB Output is correct
4 Correct 5 ms 10588 KB Output is correct
5 Correct 5 ms 10588 KB Output is correct
6 Correct 5 ms 8536 KB Output is correct
7 Correct 5 ms 8536 KB Output is correct
8 Correct 5 ms 10584 KB Output is correct
9 Correct 5 ms 8540 KB Output is correct
10 Correct 5 ms 10588 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8448 KB Output is correct
2 Correct 5 ms 8448 KB Output is correct
3 Correct 5 ms 8448 KB Output is correct
4 Correct 5 ms 10588 KB Output is correct
5 Correct 5 ms 10588 KB Output is correct
6 Correct 5 ms 8536 KB Output is correct
7 Correct 5 ms 8536 KB Output is correct
8 Correct 5 ms 10584 KB Output is correct
9 Correct 5 ms 8540 KB Output is correct
10 Correct 5 ms 10588 KB Output is correct
11 Correct 229 ms 66988 KB Output is correct
12 Correct 18 ms 66908 KB Output is correct
13 Correct 86 ms 66684 KB Output is correct
14 Correct 376 ms 67748 KB Output is correct
15 Correct 165 ms 66900 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 8448 KB Output is correct
2 Correct 5 ms 8448 KB Output is correct
3 Correct 5 ms 8448 KB Output is correct
4 Correct 5 ms 10588 KB Output is correct
5 Correct 5 ms 10588 KB Output is correct
6 Correct 5 ms 8536 KB Output is correct
7 Correct 5 ms 8536 KB Output is correct
8 Correct 5 ms 10584 KB Output is correct
9 Correct 5 ms 8540 KB Output is correct
10 Correct 5 ms 10588 KB Output is correct
11 Correct 229 ms 66988 KB Output is correct
12 Correct 18 ms 66908 KB Output is correct
13 Correct 86 ms 66684 KB Output is correct
14 Correct 376 ms 67748 KB Output is correct
15 Correct 165 ms 66900 KB Output is correct
16 Correct 290 ms 99320 KB Output is correct
17 Correct 1104 ms 102864 KB Output is correct
18 Correct 405 ms 100460 KB Output is correct
19 Correct 286 ms 99556 KB Output is correct
20 Correct 827 ms 101284 KB Output is correct