oj.uz

Submission #866328

# Submission time Handle Problem Language Result Execution time Memory
866328 2023-10-25T22:27:18 Z gutzzy Pohlepko (COCI16_pohlepko) C++14
80 / 80
 150 ms 8228 KB 
#include <bits/stdc++.h>
using namespace std;

int n;
int m;
vector<vector<char>> board;

int main(){
    cin >> n >> m;
    board = vector<vector<char>>(n,vector<char>(m));
    queue<pair<int,int>> q;
    string ans="";

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cin >> board[i][j];
        }
    }  
    
    q.push({0,0});
    ans+=board[0][0];
    for(int diagonal=0;diagonal<(m+n-2);diagonal++){
        char best='{';
        set<pair<int,int>> coords;
        while(!q.empty()){
            pair<int,int> p = q.front();
            q.pop();
            int i=p.first;
            int j=p.second;
            if(i!=n-1){
                if(board[i+1][j]<=best){
                    best=board[i+1][j];
                    coords.insert({i+1,j});
                }
            }
            if(j!=m-1){
                if(board[i][j+1]<=best){
                    best=board[i][j+1];
                    coords.insert({i,j+1});
                }
            }
        }
        ans+=best;
        for(auto coord:coords){
            if (board[coord.first][coord.second]==best){
                q.push(coord);
            }
        }
    }
    cout << ans << endl;
}

Subtask #1
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 436 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 9 ms 860 KB Output is correct
7 Correct 44 ms 2908 KB Output is correct
8 Correct 144 ms 8228 KB Output is correct
9 Correct 0 ms 352 KB Output is correct
10 Correct 3 ms 600 KB Output is correct
11 Correct 4 ms 676 KB Output is correct
12 Correct 11 ms 1116 KB Output is correct
13 Correct 7 ms 752 KB Output is correct
14 Correct 150 ms 8112 KB Output is correct
15 Correct 2 ms 348 KB Output is correct
16 Correct 104 ms 3556 KB Output is correct