oj.uz

Submission #281648

# Submission time Handle Problem Language Result Execution time Memory
281648 2020-08-23T09:35:59 Z Saacoota Robots (APIO13_robots) C++14
60 / 100
 381 ms 163844 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 int long long
#define ii pair <int , int>
#define iii1 pair <ii , int>
#define iii2 pair <int , ii>
#define TASK "AROBOT"
using   namespace   std;
const long long inf = 1e15;
const int oo = 0x3f;
int n , m , r;
long long dp[10][10][502][502];
ii null , f[502][502][4];
bool vs[502][502][4];
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][direct]) {
        res = ii(x,y);
        return res;
    }
    vs[x][y][direct] = true;
    if (s[x][y] != 'A' && s[x][y] != 'C') {
        int nx = x + dx[direct] , ny = y + dy[direct];
        if (s[nx][ny] == 'x' || nx < 1 || nx > m || ny < 1 || ny > n) 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][direct] = 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() {
    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] = inf;
    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 d = 0 ; d < r ; ++d)
    for (int i = 1 ; i <= r - d ; ++i) {
        vector < iii2 > wa;
        int j = i + d;
        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] < inf) {
                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]});
                    }
                }
            }
        }
    }
    long long ans = inf;
    for (int i = 1 ; i <= m ; ++i)
    for (int j = 1 ; j <= n ; ++j) ans = min(ans , dp[1][r][i][j]);
    if (ans < inf) cout << ans;
    else cout << -1;
}
///--------------------------
main() {
   ios::sync_with_stdio(0);
   cin.tie(0);cout.tie(0);
   readf();
   solve();
}

Compilation message

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

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 640 KB Output is correct
5 Correct 1 ms 640 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 640 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 640 KB Output is correct
5 Correct 1 ms 640 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 147 ms 102824 KB Output is correct
12 Correct 11 ms 7296 KB Output is correct
13 Correct 65 ms 66040 KB Output is correct
14 Correct 381 ms 103944 KB Output is correct
15 Correct 124 ms 102140 KB Output is correct

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 640 KB Output is correct
5 Correct 1 ms 640 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 640 KB Output is correct
11 Correct 147 ms 102824 KB Output is correct
12 Correct 11 ms 7296 KB Output is correct
13 Correct 65 ms 66040 KB Output is correct
14 Correct 381 ms 103944 KB Output is correct
15 Correct 124 ms 102140 KB Output is correct
16 Runtime error 101 ms 163844 KB Execution killed with signal 9
17 Halted 0 ms 0 KB -