oj.uz

Submission #248699

# Submission time Handle Problem Language Result Execution time Memory
248699 2020-07-13T07:44:43 Z Vladikus004 Pohlepko (COCI16_pohlepko) C++14
60 / 80
 1000 ms 65540 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]){
            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]){
            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{
        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
60.0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Correct 3 ms 5376 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 768 KB Output is correct
5 Correct 0 ms 512 KB Output is correct
6 Correct 3 ms 3968 KB Output is correct
7 Correct 9 ms 13824 KB Output is correct
8 Correct 15 ms 20480 KB Output is correct
9 Correct 1 ms 1408 KB Output is correct
10 Correct 6 ms 2432 KB Output is correct
11 Correct 9 ms 1664 KB Output is correct
12 Correct 8 ms 10496 KB Output is correct
13 Correct 13 ms 20488 KB Output is correct
14 Execution timed out 1088 ms 13752 KB Time limit exceeded
15 Runtime error 350 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 335 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)