oj.uz

Submission #372703

# Submission time Handle Problem Language Result Execution time Memory
372703 2021-03-01T10:37:15 Z maozkurt Pohlepko (COCI16_pohlepko) C++17
80 / 80
 127 ms 8556 KB 
#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.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 876 KB Output is correct
7 Correct 4 ms 3180 KB Output is correct
8 Correct 14 ms 8556 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 620 KB Output is correct
12 Correct 2 ms 1132 KB Output is correct
13 Correct 2 ms 876 KB Output is correct
14 Correct 13 ms 8556 KB Output is correct
15 Correct 2 ms 492 KB Output is correct
16 Correct 127 ms 4096 KB Output is correct