Submission #167178

#	Time	Username	Problem	Language	Result	Execution time	Memory
167178		egekabas	Pohlepko (COCI16_pohlepko)	C++14	70 / 80	294 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<ll, ll>  pii;
typedef pair<ld, ld>  pld;
int n, m;
char a[2009][2009];
bool mark[2009][2009];
string s;
vector<pii> v[4009];
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];
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= m; ++j)
            v[i-1+j-1].pb({i, j});
    mark[1][1] = 1;
    s.pb(a[1][1]);
    for(int i = 1; i <= n+m-2; ++i){
        int mini = 1e9;
        for(auto u : v[i]){
            if(mark[u.ff-1][u.ss] == 1 || mark[u.ff][u.ss-1] == 1)
                mini = min(mini, (int)a[u.ff][u.ss]);
        }
        s.pb(mini);
        for(auto u : v[i]){
            if(mark[u.ff-1][u.ss] == 1 || mark[u.ff][u.ss-1] == 1){
                if(a[u.ff][u.ss] == mini)
                    mark[u.ff][u.ss] = 1;
            }
        }
    }
    cout << s << "\n";
}

• Subtask 1: 70 / 80