oj.uz

Submission #958599

# Submission time Handle Problem Language Result Execution time Memory
958599 2024-04-06T06:17:38 Z Halym2007 Robots (APIO13_robots) C++17
100 / 100
 1108 ms 102580 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 8696 KB Output is correct
4 Correct 5 ms 10588 KB Output is correct
5 Correct 5 ms 10584 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 8696 KB Output is correct
4 Correct 5 ms 10588 KB Output is correct
5 Correct 5 ms 10584 KB Output is correct
6 Correct 5 ms 8540 KB Output is correct
7 Correct 5 ms 8444 KB Output is correct
8 Correct 6 ms 10584 KB Output is correct
9 Correct 6 ms 8544 KB Output is correct
10 Correct 6 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 8696 KB Output is correct
4 Correct 5 ms 10588 KB Output is correct
5 Correct 5 ms 10584 KB Output is correct
6 Correct 5 ms 8540 KB Output is correct
7 Correct 5 ms 8444 KB Output is correct
8 Correct 6 ms 10584 KB Output is correct
9 Correct 6 ms 8544 KB Output is correct
10 Correct 6 ms 10588 KB Output is correct
11 Correct 227 ms 66860 KB Output is correct
12 Correct 17 ms 66908 KB Output is correct
13 Correct 82 ms 66736 KB Output is correct
14 Correct 366 ms 67816 KB Output is correct
15 Correct 172 ms 66848 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 8696 KB Output is correct
4 Correct 5 ms 10588 KB Output is correct
5 Correct 5 ms 10584 KB Output is correct
6 Correct 5 ms 8540 KB Output is correct
7 Correct 5 ms 8444 KB Output is correct
8 Correct 6 ms 10584 KB Output is correct
9 Correct 6 ms 8544 KB Output is correct
10 Correct 6 ms 10588 KB Output is correct
11 Correct 227 ms 66860 KB Output is correct
12 Correct 17 ms 66908 KB Output is correct
13 Correct 82 ms 66736 KB Output is correct
14 Correct 366 ms 67816 KB Output is correct
15 Correct 172 ms 66848 KB Output is correct
16 Correct 290 ms 99496 KB Output is correct
17 Correct 1108 ms 102580 KB Output is correct
18 Correct 393 ms 100580 KB Output is correct
19 Correct 284 ms 99428 KB Output is correct
20 Correct 903 ms 101348 KB Output is correct