oj.uz

Submission #248701

# Submission time Handle Problem Language Result Execution time Memory
248701 2020-07-13T07:46:25 Z Vladikus004 Pohlepko (COCI16_pohlepko) C++14
80 / 80
 30 ms 23332 KB 
#include <bits/stdc++.h>
#define inf 2e9
#define all(v) v.begin(), v.end()
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;

const int N = 2000 + 3;
int n, m, p[N][N], was[N][N], mn[N + N];
char a[N][N];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    #ifdef LOCAL
        freopen("input.txt", "r", stdin);
    #endif // LOCAL
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    queue <int> q;
    q.push(0);
    fill(mn, mn + n + m + 2, inf);
//    memset(mn, inf, sizeof mn);
    mn[0] = a[0][0] - 'a';
    while (!q.empty()){
        int x = q.front() / m, y = q.front() % m;
        q.pop();
        was[x][y] = 1;
        if (a[x][y] - 'a' > mn[x + y]) continue;
        if (x + 1 < n && !was[x + 1][y]){
            was[x + 1][y] = 1;
            p[x + 1][y] = x * m + y;
            mn[x + y + 1] = min(mn[x + y + 1], a[x + 1][y] - 'a');
            q.push((x + 1) * m + y);
        }
        if (y + 1 < m && !was[x][y + 1]){
            was[x][y + 1] = 1;
            p[x][y + 1] = x * m + y;
            mn[x + y + 1] = min(mn[x + y + 1], a[x][y + 1] - 'a');
            q.push(x * m + y + 1);
        }
    }
    vector <char> way;
    way.push_back(a[n - 1][m - 1]);
    int x = (n - 1) * m + m - 1;
    do{
        if (!x) break;
        x = p[x / m][x % m];
//        cout << a[x / m][x % m] << "!\n";
        way.push_back(a[x / m][x % m]);
    }while (x);
    reverse(all(way));
    for (auto u: way) cout << u;
}

Subtask #1
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 4 ms 5376 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 768 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 4 ms 3840 KB Output is correct
7 Correct 12 ms 13696 KB Output is correct
8 Correct 17 ms 20344 KB Output is correct
9 Correct 1 ms 1280 KB Output is correct
10 Correct 1 ms 2432 KB Output is correct
11 Correct 1 ms 1536 KB Output is correct
12 Correct 6 ms 10368 KB Output is correct
13 Correct 11 ms 20352 KB Output is correct
14 Correct 15 ms 20352 KB Output is correct
15 Correct 1 ms 1536 KB Output is correct
16 Correct 30 ms 23332 KB Output is correct