oj.uz

Submission #98534

# Submission time Handle Problem Language Result Execution time Memory
98534 2019-02-23T21:15:35 Z dalgerok Pohlepko (COCI16_pohlepko) C++17
80 / 80
 66 ms 13836 KB 
#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.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 640 KB Output is correct
2 Correct 4 ms 2432 KB Output is correct
3 Correct 2 ms 512 KB Output is correct
4 Correct 3 ms 640 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 9 ms 2048 KB Output is correct
7 Correct 22 ms 7168 KB Output is correct
8 Correct 65 ms 12408 KB Output is correct
9 Correct 3 ms 896 KB Output is correct
10 Correct 6 ms 1332 KB Output is correct
11 Correct 6 ms 1152 KB Output is correct
12 Correct 11 ms 4736 KB Output is correct
13 Correct 16 ms 8576 KB Output is correct
14 Correct 55 ms 12380 KB Output is correct
15 Correct 4 ms 896 KB Output is correct
16 Correct 66 ms 13836 KB Output is correct