oj.uz

Submission #1106767

# Submission time Handle Problem Language Result Execution time Memory
1106767 2024-10-31T03:24:42 Z vjudge1 Pohlepko (COCI16_pohlepko) C++14
10 / 80
 1000 ms 36500 KB 
#include <bits/stdc++.h>
#define sts(v) svble_sort(v.BE, v.E)
#define Rsts(v) svble_sort(v.rBE, v.rE)
#define rev(v) reverse(v.BE, v.E)
#define BE begin()
#define rBE rbegin()
#define E end()
#define rE rend()
#define pb push_back
#define ppb pop_back()
#define pf push_front
#define ppf pop_front()
#define F first
#define S second

using namespace std;
using ll = long long;

const int MAXN = 2e3 + 1;
const int MOD = 1e9 + 7;

vector<vector<char>> v(MAXN, vector<char> (MAXN));
pair<int, int> ans[MAXN][MAXN];
vector<vector<bool>> cmp(MAXN, vector<bool> (MAXN));
int n, m;

void dij(){
    priority_queue<pair<int, pair<pair<int, pair<int, int>>, pair<int, int>>>> q;
    q.push({1, {{v[1][1] - '0', {-1, -1}}, {1, 1}}});

    while(q.size()){
        int x = q.top().S.S.F, y = q.top().S.S.S, cnt = abs(q.top().F);
        pair<int, int> anterior = q.top().S.F.S;
        q.pop();

        if(x > n or y > m or cmp[x][y])continue;
        cmp[x][y] = 1;
        ans[x][y] = anterior;

        q.push({-(cnt + 1), {{-(v[x][y] - '0'), {x, y}}, {x + 1, y}}});
        q.push({-(cnt + 1), {{-(v[x][y] - '0'), {x, y}}, {x, y + 1}}});
    }
}

int main(){
    ios_base::sync_with_stdio(0); 
    cin.tie(0); cout.tie(0);

    cin >> n >> m;

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++){
            char c; cin >> c;

            v[i][j] = c;
        }

    dij();

    string res = "";
    

    while(n > 0){
        res.pb(v[n][m]);
        int N = ans[n][m].F, M = ans[n][m].S;
        n = N; m = M;
    }
    rev(res);

    cout << res << '\n';

    return 0;
}

Subtask #1
10.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4944 KB Output is correct
2 Correct 7 ms 13308 KB Output is correct
3 Incorrect 5 ms 4944 KB Output isn't correct
4 Incorrect 5 ms 6992 KB Output isn't correct
5 Incorrect 7 ms 5372 KB Output isn't correct
6 Incorrect 66 ms 11344 KB Output isn't correct
7 Incorrect 392 ms 27720 KB Output isn't correct
8 Execution timed out 1074 ms 36500 KB Time limit exceeded
9 Incorrect 6 ms 6992 KB Output isn't correct
10 Incorrect 19 ms 9212 KB Output isn't correct
11 Incorrect 35 ms 7232 KB Output isn't correct
12 Incorrect 95 ms 21592 KB Output isn't correct
13 Incorrect 52 ms 35904 KB Output isn't correct
14 Execution timed out 1068 ms 36400 KB Time limit exceeded
15 Incorrect 7 ms 6992 KB Output isn't correct
16 Incorrect 342 ms 29772 KB Output isn't correct