제출 #371230

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
371230		maozkurt	Pohlepko (COCI16_pohlepko)	C++17	20 / 80	963 ms	35820 KiB

pohlepko

#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 / 80