Submission #1106767

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106767		vjudge1	Pohlepko (COCI16_pohlepko)	C++14	10 / 80	1074 ms	36500 KiB

pohlepko

#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 / 80