oj.uz

Submission #850529

# Submission time Handle Problem Language Result Execution time Memory
850529 2023-09-16T20:16:17 Z abdo3066 Robots (APIO13_robots) C++14
100 / 100
 530 ms 100176 KB 
#include    <bits/stdc++.h>
#define fo(i,a,b) for(int i=(a);i<=(b);++i)
#define fd(i,a,b) for(int i=(a);i>=(b);--i)
#define rep(i,a,b)  for(int i=(a);i<(b);++i)
#define fi  first
#define se  second
#define LL  unsigned long long
#define uint unsigned int
#define pb  push_back
#define eb  emplace_back
#define bit(s,i) ((s >> i) & 1)
#define off(s,i) (s & (~ (1 << i)))
#define ii pair <int , int>
#define iii1 pair <ii , int>
#define iii2 pair <int , ii>
#define TASK "AROBOT"
using   namespace   std;
const int oo = 1e9 + 5;
int n , m , r;
int dp[10][10][502][502];
ii null , f[502][502][4];
bool vs[502][502];
string s[502];
int dx[] = { 0 , -1 , 0 , 1};
int dy[] = { 1 , 0 , -1 , 0};
///--------------------------
ii F(int x,int y,int direct) {
    if (f[x][y][direct] != null) return f[x][y][direct];
    ii &res = f[x][y][direct];
    if (vs[x][y]) {
        res = ii(x,y);
        return res;
    }
    vs[x][y] = true;
    if (s[x][y] != 'A' && s[x][y] != 'C') {
        int nx = x + dx[direct] , ny = y + dy[direct];
        if (nx < 1 || nx > m || ny < 1 || ny > n || s[nx][ny] == 'x') res = ii(x , y);
        else res = F(nx , ny , direct);
    } else {
        int ndirect = direct;
        if (s[x][y] == 'A') ndirect++;
        else ndirect--;
        ndirect = (ndirect + 4) % 4;
        int nx = x + dx[ndirect] , ny = y + dy[ndirect];
        if (nx < 1 || nx > m || ny < 1 || ny > n || s[nx][ny] == 'x') res = ii(x , y);
        else res = F(nx , ny , ndirect);
    }
    vs[x][y] = false;
    return res;
}
///--------------------------
void readf() {
    cin >> r >> n >> m ;
    for (int i = 1 ; i <= m ; ++i) {
        cin >> s[i];
        s[i] = " " + s[i];
    }
}
///--------------------------
void solve() {
    null = ii(0,0);
    for (int i = 1 ; i <= r ; ++i)
    for (int j = 1 ; j <= r ; ++j)
    for (int x = 1 ; x <= m ; ++x)
    for (int y = 1 ; y <= n ; ++y) dp[i][j][x][y] = oo;
    for (int i = 1 ; i <= m ; ++i)
    for (int j = 1 ; j <= n ; ++j) {
        if (s[i][j] != 'x') {
            for (int k = 0 ; k < 4 ; ++k)
            if (f[i][j][k] == null) f[i][j][k] = F(i , j , k);
        }
        if ('1' <= s[i][j] && s[i][j] <= '9') dp[s[i][j] - '0'][s[i][j] - '0'][i][j] = 0;
    }
    for (int i = r ; i > 0 ; --i) 
    for (int j = i ; j <= r ; ++j) {
        vector < iii2 > wa;
        for (int x = 1 ; x <= m ; ++x)
        for (int y = 1 ; y <= n ; ++y) {
            for (int k = i ; k < j ; ++k)
            dp[i][j][x][y] = min(dp[i][j][x][y] , dp[i][k][x][y] + dp[k+1][j][x][y]);
            if (dp[i][j][x][y] < oo) {
                wa.pb({dp[i][j][x][y] , {x , y}});
            }
        }
        stack < iii2 > stk , pa;
        sort(wa.rbegin(),wa.rend());
        for (auto x : wa) stk.push(x);
        while (!stk.empty()) {
            int val = stk.top().fi;
            while (!stk.empty() && stk.top().fi == val) {
                pa.push(stk.top());
                stk.pop();
            }
            while (!pa.empty()) {
                int x = pa.top().se.fi , y = pa.top().se.se;
                pa.pop();
                for (int k = 0 ; k < 4 ; ++k) {
                    int nx = f[x][y][k].fi , ny = f[x][y][k].se;
                    if (nx == x && ny == y) continue;
                    if (dp[i][j][nx][ny] > val + 1) {
                        dp[i][j][nx][ny] = val + 1;
                        stk.push({val + 1 , f[x][y][k]});
                    }
                }
            }
        }
    }
    int ans = oo;
    for (int i = 1 ; i <= m ; ++i)
    for (int j = 1 ; j <= n ; ++j) ans = min(ans , dp[1][r][i][j]);
    if (ans < oo) cout << ans;
    else cout << -1;
}
main() {
   ios::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   readf();
   solve();
}/////////////////////////////////////////////////////////////

Compilation message

robots.cpp:114:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  114 | main() {
      | ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8552 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8728 KB Output is correct
5 Correct 1 ms 8536 KB Output is correct

Subtask #2
20.0 / 20.0

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

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8552 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8728 KB Output is correct
5 Correct 1 ms 8536 KB Output is correct
6 Correct 2 ms 8672 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Correct 65 ms 94188 KB Output is correct
12 Correct 4 ms 8024 KB Output is correct
13 Correct 22 ms 66396 KB Output is correct
14 Correct 178 ms 95036 KB Output is correct
15 Correct 44 ms 93836 KB Output is correct

Subtask #4
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8552 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8728 KB Output is correct
5 Correct 1 ms 8536 KB Output is correct
6 Correct 2 ms 8672 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Correct 65 ms 94188 KB Output is correct
12 Correct 4 ms 8024 KB Output is correct
13 Correct 22 ms 66396 KB Output is correct
14 Correct 178 ms 95036 KB Output is correct
15 Correct 44 ms 93836 KB Output is correct
16 Correct 67 ms 97372 KB Output is correct
17 Correct 530 ms 100176 KB Output is correct
18 Correct 90 ms 97788 KB Output is correct
19 Correct 63 ms 97496 KB Output is correct
20 Correct 296 ms 99204 KB Output is correct