Submission #866328

#	Time	Username	Problem	Language	Result	Execution time	Memory
866328		gutzzy	Pohlepko (COCI16_pohlepko)	C++14	80 / 80	150 ms	8228 KiB

pohlepko

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