Submission #372703

#	Time	Username	Problem	Language	Result	Execution time	Memory
372703		maozkurt	Pohlepko (COCI16_pohlepko)	C++17	80 / 80	127 ms	8556 KiB

pohlepko

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <numeric>
#include <cassert>

#define endl '\n'
#define sp ' '

#define pb push_back
#define mp make_pair
#define ff first
#define ss second

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int maxn = 2005;

string arr[maxn];

int main(){
    
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cerr.tie(nullptr);
    int n,m;cin>>n>>m;
    for(int i=0;i<n;i++)
        cin>>arr[i];
    
    string ans = "";

    ans += arr[0][0];
    set<pii> coord;
    coord.insert({0,0});
    
    while(!coord.empty()){
        char low = 'z'+1;
        set<pii> s;
        for(pii i : coord){
            if(i.ff<n-1){
                low = min(low, arr[i.ff+1][i.ss]);
            }
            if(i.ss<m-1){
                low = min(low,arr[i.ff][i.ss+1]);
            }
        }
        if(low == 'z'+1)
            break;
        ans += low;
        for(pii i : coord){
            if(i.ff<n-1){
                if(arr[i.ff+1][i.ss] == low){
                    s.emplace(i.ff+1,i.ss);
                }
            }
            if(i.ss < m-1){
                if(arr[i.ff][i.ss+1] == low){
                    s.emplace(i.ff,i.ss+1);
                }
            }
        }
        coord = s;
    }
    cout << ans << endl;
}

• Subtask 1: 80 / 80