oj.uz

Submission #909164

# Submission time Handle Problem Language Result Execution time Memory
909164 2024-01-17T05:51:13 Z Sir_Ahmed_Imran Robots (APIO13_robots) C++17
30 / 100
 342 ms 129152 KB 
                              ///~~~LOTA~~~///
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define ff first
#define ss second
#define ll long long 
#define append push_back
#define pii pair<long long,long long>
#define all(x) (x).begin(),(x).end()
#define int long long
#define N 502
#define M 10
int n,m,o;
char c[N][N];
vector<pii> a[N][N];
int dist[N][N][M][M];
void mark(int x,int y,int p,int q,int r,int s){
    if(!x || x>n || !y || y>m) return;
    if(c[x][y]=='x'){
        p=x+r;
        q=y+s;
    }
    else if(p!=x || q!=y)
        a[x][y].append({p,q});
    if(c[x][y]=='C'){
        swap(r,s);
        r=-r;
    }
    if(c[x][y]=='A'){
        swap(r,s);
        s=-s;
    }
    mark(x+r,y+s,p,q,r,s);
}
void dijkstra(int l,int r){
    int d,p,q;
    priority_queue<pair<int,pii>,vector<pair<int,pii>>,greater<pair<int,pii>>> Q;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(dist[i][j][l][r]<1e17)
                Q.push({dist[i][j][l][r],{i,j}});
    while(!Q.empty()){
        d=Q.top().ff;
        p=Q.top().ss.ff;
        q=Q.top().ss.ss;
        Q.pop();
        if(d==dist[p][q][l][r]){
            for(auto& i:a[p][q]){
                if(d+1<dist[i.ff][i.ss][l][r]){
                    dist[i.ff][i.ss][l][r]=d+1;
                    Q.push({d+1,i});
                }
            }
        }
    }
}
void solve(){
    int s;
    cin>>o>>m>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            cin>>c[i][j];
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            for(int l=1;l<=o;l++)
                for(int r=l;r<=o;r++)
                    dist[i][j][l][r]=1e17;
    for(int i=1;i<=n;i++){
        mark(i,1,i,1,0,1);
        mark(i,m,i,m,0,-1);
    }
    for(int i=1;i<=m;i++){
        mark(1,i,1,i,1,0);
        mark(n,i,n,i,-1,0);
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            s=c[i][j]-'0';
            if(s>0 && s<10){
                dist[i][j][s][s]=0;
                dijkstra(s,s);
            }
        }
    }
    for(int j=1;j<o;j++){
        for(int i=1;i+j<=o;i++){
            for(int p=1;p<=n;p++)
                for(int q=1;q<=m;q++)
                    for(int d=i;d<i+j;d++)
                        dist[p][q][i][i+j]=min(dist[p][q][i][i+j]
                            ,dist[p][q][i][d]+dist[p][q][d+1][i+j]);
            dijkstra(i,i+j);
        }
    }
    s=1e17;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            s=min(s,dist[i][j][1][o]);
    if(s==1e17) s=-1;
    cout<<s;
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(NULL);
    solve();
    return 0;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
20.0 / 20.0

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

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 3 ms 8540 KB Output is correct
3 Correct 2 ms 8668 KB Output is correct
4 Correct 3 ms 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8624 KB Output is correct
8 Correct 3 ms 8540 KB Output is correct
9 Correct 3 ms 8536 KB Output is correct
10 Correct 3 ms 10584 KB Output is correct
11 Correct 342 ms 129152 KB Output is correct
12 Correct 39 ms 127680 KB Output is correct
13 Correct 135 ms 127768 KB Output is correct
14 Incorrect 231 ms 127204 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #4
0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8540 KB Output is correct
2 Correct 3 ms 8540 KB Output is correct
3 Correct 2 ms 8668 KB Output is correct
4 Correct 3 ms 10588 KB Output is correct
5 Correct 2 ms 10588 KB Output is correct
6 Correct 2 ms 8540 KB Output is correct
7 Correct 2 ms 8624 KB Output is correct
8 Correct 3 ms 8540 KB Output is correct
9 Correct 3 ms 8536 KB Output is correct
10 Correct 3 ms 10584 KB Output is correct
11 Correct 342 ms 129152 KB Output is correct
12 Correct 39 ms 127680 KB Output is correct
13 Correct 135 ms 127768 KB Output is correct
14 Incorrect 231 ms 127204 KB Output isn't correct
15 Halted 0 ms 0 KB -