Submission #167165

#	Time	Username	Problem	Language	Result	Execution time	Memory
167165		egekabas	Pohlepko (COCI16_pohlepko)	C++14	65 / 80	1077 ms	65540 KiB

pohlepko

#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long   ll;
typedef unsigned long long   ull;
typedef long double ld;
typedef pair<ll, ll>    pll;
typedef pair<ull, ull>    pull;
typedef pair<int, int>  pii;
typedef pair<ld, ld>  pld;
int n, m;
char a[2009][2009];
int cur;
vector<pii> v[2];
string s;
    
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
    
    cin >> n >> m;
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            cin >> a[i][j];
    s.pb(a[1][1]);
    v[cur].pb({1, 1});
    while(1){
        int mini = 1e9;
        for(auto u : v[cur]){
            if(u == mp(n, m))
                goto END;
            if(u.ff+1 <= n)
                mini = min((int)a[u.ff+1][u.ss], mini);
            if(u.ss+1 <= m)
                mini = min((int)a[u.ff][u.ss+1], mini);
        }
        s.pb(mini);
        for(auto u : v[cur]){
            if(u.ff+1 <= n && a[u.ff+1][u.ss] == mini)
                v[cur^1].pb({u.ff+1, u.ss});
            if(u.ss+1 <= m && a[u.ff][u.ss+1] == mini)
                v[cur^1].pb({u.ff, u.ss+1});
        }
        v[cur].clear();
        cur ^= 1;;
    }
    END:;
    cout << s << "\n";
}

• Subtask 1: 65 / 80