oj.uz

Submission #371230

# Submission time Handle Problem Language Result Execution time Memory
371230 2021-02-26T08:22:31 Z maozkurt Pohlepko (COCI16_pohlepko) C++17
20 / 80
 963 ms 35820 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;

char arr[maxn][maxn];
int d[maxn][maxn];
int p[maxn][maxn];
const int inf = 1e9;
int n,m;
void dijkstra(){
    using paa = pair<int,pii>;
    priority_queue<paa,vector<paa>,greater<paa>> q;
    
    fill(&d[0][0],&d[n-1][m-1] + 1,inf);
    d[0][0] = 0;
    q.push({0,{0,0}});

    while(q.size()){
        int curd = q.top().ff;
        int curi = q.top().ss.ff;
        int curj = q.top().ss.ss;
        q.pop();
        if(curd != d[curi][curj])
            continue;

        if(curi<n-1){
            if(d[curi+1][curj] > d[curi][curj] + arr[curi][curj]){
                d[curi+1][curj] = d[curi][curj] + arr[curi][curj];
                q.push({d[curi+1][curj],{curi+1,curj}});
                p[curi+1][curj] = 1;
            }
        }

        if(curj<m-1){
            if(d[curi][curj+1] > d[curi][curj] + arr[curi][curj]){
                d[curi][curj+1] = d[curi][curj] + arr[curi][curj];
                q.push({d[curi][curj+1],{curi,curj+1}});
                p[curi][curj+1] = -1;
            }
        }
    }
}

int main(){
    
    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cerr.tie(nullptr);
    
    cin>>n>>m;
    for(int i=0;i<n;i++)
        cin >> arr[i];
    
    dijkstra();
    
    /*
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            cout << p[i][j] << sp;
        }
        cout << endl;
    } 
    */
    int i=n-1,j=m-1;
    string ans;
    ans += arr[i][j];
    while(i!=0 || j!=0){
        if(p[i][j] == 1){
            ans.pb((char)(d[i][j] - d[i-1][j]));
            i--;
        }
        else if(p[i][j] == -1){
            ans.pb((char)(d[i][j] - d[i][j-1]));
            j--;
        }
        else
            abort();
    }
    for(int c=(int)ans.size()-1;c>=0;c--){
        cout << ans[c];
    }
    cout << endl;
    
}

Subtask #1
20.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 5 ms 7276 KB Output is correct
3 Incorrect 1 ms 512 KB Output isn't correct
4 Incorrect 1 ms 876 KB Output isn't correct
5 Incorrect 1 ms 492 KB Output isn't correct
6 Incorrect 43 ms 6124 KB Output isn't correct
7 Incorrect 291 ms 24044 KB Output isn't correct
8 Incorrect 963 ms 35820 KB Output isn't correct
9 Incorrect 2 ms 1772 KB Output isn't correct
10 Incorrect 13 ms 3436 KB Output isn't correct
11 Incorrect 18 ms 2540 KB Output isn't correct
12 Incorrect 66 ms 15468 KB Output isn't correct
13 Incorrect 41 ms 28780 KB Output isn't correct
14 Incorrect 932 ms 35820 KB Output isn't correct
15 Correct 3 ms 1772 KB Output is correct
16 Correct 200 ms 26860 KB Output is correct