oj.uz

Submission #846539

# Submission time Handle Problem Language Result Execution time Memory
846539 2023-09-07T19:15:52 Z Saacoota Robots (APIO13_robots) C++14
100 / 100
 507 ms 99912 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:115:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  115 | main() {
      | ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8544 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8548 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8544 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8548 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 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 1 ms 8668 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8544 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8548 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 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 1 ms 8668 KB Output is correct
11 Correct 68 ms 94184 KB Output is correct
12 Correct 6 ms 8028 KB Output is correct
13 Correct 21 ms 66272 KB Output is correct
14 Correct 175 ms 94816 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 2 ms 8544 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8548 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 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 1 ms 8668 KB Output is correct
11 Correct 68 ms 94184 KB Output is correct
12 Correct 6 ms 8028 KB Output is correct
13 Correct 21 ms 66272 KB Output is correct
14 Correct 175 ms 94816 KB Output is correct
15 Correct 44 ms 93836 KB Output is correct
16 Correct 63 ms 97372 KB Output is correct
17 Correct 507 ms 99912 KB Output is correct
18 Correct 87 ms 97788 KB Output is correct
19 Correct 59 ms 97496 KB Output is correct
20 Correct 289 ms 99060 KB Output is correct