Submission #98534

#	Time	Username	Problem	Language	Result	Execution time	Memory
98534		dalgerok	Pohlepko (COCI16_pohlepko)	C++17	80 / 80	66 ms	13836 KiB

pohlepko

#include<bits/stdc++.h>
using namespace std;


const int N = 2e3 + 5;



int n, m;
bool used[N][N];
char a[N][N];
vector < pair < int, int > > q[N + N];

inline bool check(int x, int y){
    return 1 <= x && x <= n && 1 <= y && y <= m;
}

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++){
            cin >> a[i][j];
        }
    }
    q[1 + 1].push_back(make_pair(1, 1));
    for(int i = 2; i <= n + m; i++){
        cout << a[q[i][0].first][q[i][0].second];
        char mn = 'z';
        for(auto it : q[i]){
            int xx, yy;
            xx = it.first + 1, yy = it.second;
            if(check(xx, yy)){
                mn = min(mn, a[xx][yy]);
            }
            xx = it.first, yy = it.second + 1;
            if(check(xx, yy)){
                mn = min(mn, a[xx][yy]);
            }
        }
        for(auto it : q[i]){
            int xx, yy;
            xx = it.first + 1, yy = it.second;
            if(check(xx, yy) && !used[xx][yy] && a[xx][yy] == mn){
                used[xx][yy] = true;
                q[xx + yy].push_back(make_pair(xx, yy));
            }
            xx = it.first, yy = it.second + 1;
            if(check(xx, yy) && !used[xx][yy] && a[xx][yy] == mn){
                used[xx][yy] = true;
                q[xx + yy].push_back(make_pair(xx, yy));
            }
        }
    }
}

• Subtask 1: 80 / 80