oj.uz

답안 #1068667

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1068667 2024-08-21T11:16:12 Z vjudge1 Text editor (CEOI24_editor) C++17
0 / 100
 52 ms 80684 KB 
#include <bits/stdc++.h>
#define div /
#define ll long long

#define fore(i, l, r) for(int i=int(l); i<int(r); i++)
#define sz(a) int((a).size())

using namespace std;

const int INF = 1e9;
const int MX = 5e5 + 23;
const int MOD = 1000000007;
const int MAX_N = 5e5+23;
const int N = 1e6;

int grid[1005][5005],dist[1005][5005],visited[1005][5005],oznacen[1005][5005];

void solve() {
    int n; cin >> n;
    int sl,sc,el,ec;
    cin >> sl >> sc >> el >> ec;
    int l[n];
    fore(i,0,1003) {
        fore(j,0,5003) {
            dist[i][j] = INF;
            grid[i][j] = 1e6;
        }
    }
    fore(i,1,n+1) {
        cin >> l[i];
        fore(j,1,l[i]+1)
            grid[i][j] = 1;
    }
    queue<pair<int,int>> q;
    dist[sl][sc] = 0;
    visited[sl][sc] = 1;
    q.push({sl,sc});
    while(!q.empty()) {
        pair<int,int> s=q.front(); q.pop();
        int SL = s.first, SC = s.second;
        if(SL+1 <= n) {
            if(grid[SL+1][SC] < 1e6) {
                dist[SL+1][SC] = min(dist[SL+1][SC], dist[SL][SC] + grid[SL+1][SC]);
                if(!visited[SL+1][SC])
                    q.push({SL+1,SC});
                visited[SL+1][SC] = 1;
            } else {
                dist[SL+1][l[SL+1]] = min(dist[SL+1][l[SL+1]], dist[SL][SC] + 1);
                if(!oznacen[SL+1][l[SL+1]])
                    q.push({SL+1,l[SL+1]});
                oznacen[SL+1][l[SL+1]] = 1;
            }
        }
        if(SL-1 > 0) {
            if(grid[SL-1][SC] < 1e6) {
                dist[SL-1][SC] = min(dist[SL-1][SC], dist[SL][SC] + grid[SL-1][SC]);
                if(!visited[SL-1][SC])
                    q.push({SL-1,SC});
                visited[SL-1][SC] = 1;
            } else {
                dist[SL-1][l[SL-1]] = min(dist[SL-1][l[SL-1]], dist[SL][SC] + 1);
                if(!oznacen[SL-1][l[SL-1]])
                    q.push({SL-1,l[SL-1]});
                oznacen[SL-1][l[SL-1]] = 1;
            }
        }
        if(SC+1 <= 5001) {
            if(grid[SL][SC+1] < 1e6) {
                dist[SL][SC+1] = min(dist[SL][SC+1], dist[SL][SC] + grid[SL][SC+1]);
                if(!visited[SL][SC+1])
                    q.push({SL,SC+1});
                visited[SL][SC+1] = 1;
            }
        }
        if(SC-1 > 0) {
            if(grid[SL][SC-1] < 1e6) {
                dist[SL][SC-1] = min(dist[SL][SC-1], dist[SL][SC] + grid[SL][SC-1]);
                if(!visited[SL][SC-1])
                    q.push({SL,SC-1});
                visited[SL][SC-1] = 1;
            }
        }
        if(SC == 1 and SL > 1 and SL <= n) { // SPECIAL LEFT PRESS
            dist[SL-1][l[SL-1]] = min(dist[SL-1][l[SL-1]], dist[SL][SC] + 1);
            if(!oznacen[SL-1][l[SL-1]])
                q.push({SL-1,l[SL-1]});
            oznacen[SL-1][l[SL-1]] = 1;
        }
        if(SC == l[SL-1] and SL < n) { // SPECIAL RIGHT PRESS
            dist[SL+1][1] = min(dist[SL+1][1], dist[SL][SC] + 1);
            if(!oznacen[SL+1][1])
                q.push({SL+1, 1});
            oznacen[SL+1][1] = 1;
        }
    }
    cout << dist[el][ec] << endl;
}

int main() {
    ios::sync_with_stdio(false);

    int t=1;
    while(t--) solve();
}

Subtask #0
0.0 / 0.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 42076 KB Output is correct
2 Correct 8 ms 42000 KB Output is correct

Subtask #1
0.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 41820 KB Output is correct
2 Runtime error 43 ms 80684 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 42076 KB Output is correct
2 Correct 8 ms 42000 KB Output is correct
3 Correct 8 ms 41820 KB Output is correct
4 Correct 39 ms 57424 KB Output is correct
5 Incorrect 52 ms 55892 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 42076 KB Output is correct
2 Correct 8 ms 42000 KB Output is correct
3 Correct 8 ms 41820 KB Output is correct
4 Runtime error 43 ms 80684 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #4
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 8 ms 41820 KB Output is correct
2 Runtime error 43 ms 80684 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 44.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 42076 KB Output is correct
2 Correct 8 ms 42000 KB Output is correct
3 Correct 8 ms 41820 KB Output is correct
4 Runtime error 43 ms 80684 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -