Submission #167178

# Submission time Handle Problem Language Result Execution time Memory
167178 2019-12-06T08:08:40 Z egekabas Pohlepko (COCI16_pohlepko) C++14
70 / 80
294 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<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";
}
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 2424 KB Output is correct
3 Correct 2 ms 504 KB Output is correct
4 Correct 3 ms 760 KB Output is correct
5 Correct 3 ms 760 KB Output is correct
6 Correct 19 ms 7416 KB Output is correct
7 Correct 113 ms 31608 KB Output is correct
8 Runtime error 291 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
9 Correct 3 ms 1020 KB Output is correct
10 Correct 7 ms 2552 KB Output is correct
11 Correct 10 ms 3064 KB Output is correct
12 Correct 32 ms 12288 KB Output is correct
13 Correct 21 ms 12408 KB Output is correct
14 Runtime error 294 ms 65540 KB Execution killed with signal 9 (could be triggered by violating memory limits)
15 Correct 3 ms 1144 KB Output is correct
16 Correct 137 ms 38392 KB Output is correct