oj.uz

Submission #167165

# Submission time Handle Problem Language Result Execution time Memory
167165 2019-12-06T07:28:59 Z egekabas Pohlepko (COCI16_pohlepko) C++14
65 / 80
 1000 ms 65540 KB 
#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.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 1400 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 6 ms 1144 KB Output is correct
7 Correct 23 ms 2972 KB Output is correct
8 Correct 63 ms 4216 KB Output is correct
9 Correct 2 ms 504 KB Output is correct
10 Correct 6 ms 764 KB Output is correct
11 Correct 10 ms 632 KB Output is correct
12 Correct 10 ms 2296 KB Output is correct
13 Correct 10 ms 4216 KB Output is correct
14 Execution timed out 1077 ms 18808 KB Time limit exceeded
15 Runtime error 234 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
16 Runtime error 279 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)