Submission #1106771

#	Time	Username	Problem	Language	Result	Execution time	Memory
1106771		vjudge1	Pohlepko (COCI16_pohlepko)	C++14	80 / 80	44 ms	8988 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));
vector<char> ans(MAXN * MAXN + 1, 'z' + 1);
vector<vector<bool>> cmp(MAXN, vector<bool> (MAXN));
int n, m;

int dij(){
    queue<pair<pair<int, char>, pair<int, int>>> q;
    q.push({{1, 'z' + 1}, {1, 1}});
    int max_prof = 0;

    while(q.size()){
        int x = q.front().S.F, y = q.front().S.S, prof = q.front().F.F;
        char last = q.front().F.S;
        q.pop();

        if(last != ans[prof - 1] or x > n or y > m or cmp[x][y])continue;
        cmp[x][y] = 1;
        ans[prof] = min(ans[prof], v[x][y]);
        max_prof = max(max_prof, prof);

        q.push({{prof + 1, v[x][y]}, {x + 1, y}});
        q.push({{prof + 1, v[x][y]}, {x, y + 1}});
    }
    return max_prof;
}

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;
        }

    int N = dij();
    
    for(int i = 1; i <= N; i++)
        cout << ans[i];

    return 0;
}

• Subtask 1: 80 / 80