Submission #248701

#	Time	Username	Problem	Language	Result	Execution time	Memory
248701		Vladikus004	Pohlepko (COCI16_pohlepko)	C++14	80 / 80	30 ms	23332 KiB

pohlepko

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