제출 #1165538

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1165538		HappyCapybara	웜뱃 (IOI13_wombats)	C++20	39 / 100	20070 ms	10176 KiB

wombats

#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;

int R, C;
vector<vector<int>> d, l, r;
vector<vector<int>> res;

void calc(){
    for (int i=0; i<C; i++){
        vector<vector<bool>> seen(R, vector<bool>(C, false));
        priority_queue<pair<int,pair<int,int>>> pq;
        pq.push({0, {0, i}});
        while (!pq.empty()){
            int dist = -pq.top().first, x = pq.top().second.first, y = pq.top().second.second;
            pq.pop();
            if (seen[x][y]) continue;
            seen[x][y] = true;
            if (x == R-1) res[i][y] = dist;
            else pq.push({-(dist+d[x][y]), {x+1, y}});
            if (y > 0) pq.push({-(dist+l[x][y]), {x, y-1}});
            if (y < C-1) pq.push({-(dist+r[x][y]), {x, y+1}});
        }
    }
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
    ::R = R; ::C = C;
    d.resize(R, vector<int>(C));
    l.resize(R, vector<int>(C));
    r.resize(R, vector<int>(C));
    for (int i=0; i<R; i++){
        for (int j=0; j<C; j++){
            if (i < R-1) d[i][j] = V[i][j];
            if (j > 0) l[i][j] = H[i][j-1];
            if (j < C-1) r[i][j] = H[i][j];
        }
    }
    res.resize(C, vector<int>(C));
    calc();
}

void changeH(int P, int Q, int W) {
    r[P][Q] = W;
    l[P][Q+1] = W;
    calc();
}

void changeV(int P, int Q, int W) {
    d[P][Q] = W;
    calc();
}

int escape(int V1, int V2) {
    return res[V1][V2];
}

• Subtask 1: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 0 / 16
• Subtask 4: 18 / 18
• Subtask 5: 0 / 21
• Subtask 6: 0 / 24