oj.uz

Submission #1106771

# Submission time Handle Problem Language Result Execution time Memory
1106771 2024-10-31T03:53:45 Z vjudge1 Pohlepko (COCI16_pohlepko) C++14
80 / 80
 44 ms 8988 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));
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.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8784 KB Output is correct
2 Correct 6 ms 8784 KB Output is correct
3 Correct 6 ms 8952 KB Output is correct
4 Correct 6 ms 8784 KB Output is correct
5 Correct 6 ms 8784 KB Output is correct
6 Correct 8 ms 8784 KB Output is correct
7 Correct 16 ms 8988 KB Output is correct
8 Correct 44 ms 8784 KB Output is correct
9 Correct 7 ms 8784 KB Output is correct
10 Correct 7 ms 8784 KB Output is correct
11 Correct 7 ms 8784 KB Output is correct
12 Correct 9 ms 8784 KB Output is correct
13 Correct 8 ms 8984 KB Output is correct
14 Correct 39 ms 8784 KB Output is correct
15 Correct 7 ms 8844 KB Output is correct
16 Correct 31 ms 8984 KB Output is correct