제출 #768667

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
768667		boris_mihov	Wombats (IOI13_wombats)	C++17	37 / 100	20076 ms	15800 KiB

wombats

#include "wombats.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <vector>
#include <queue>

typedef long long llong;
const int MAXR = 5000 + 10;
const int MAXC = 100 + 10;
const int INF  = 2e9;

int r, c;
int costLeft[MAXR][MAXC];
int costDown[MAXR][MAXC];
int dp[MAXC][MAXR][MAXC];
int prefix[MAXR];
int suffix[MAXR];

struct Element
{
    int row;
    int col;
    int dist;

    friend bool operator < (const Element &a, const Element &b)
    {
        return a.dist > b.dist;
    }
};

int dist[MAXC][MAXC];
int dist2[MAXR][MAXC];
std::priority_queue <Element> pq;
bool small = false;

void dijkstra(int col)
{
    for (int i = 1 ; i <= r ; ++i)
    {
        for (int j = 1 ; j <= c ; ++j)
        {
            dist2[i][j] = INF;
        }
    }

    dist2[1][col] = 0;
    pq.push({1, col, 0});

    while (!pq.empty())
    {
        auto [row, col, d] = pq.top();
        pq.pop();

        if (col > 1 && dist2[row][col - 1] > d + costLeft[row][col - 1])
        {
            dist2[row][col - 1] = d + costLeft[row][col - 1];
            pq.push({row, col - 1, dist2[row][col - 1]});
        }

        if (col < c && dist2[row][col + 1] > d + costLeft[row][col])
        {
            dist2[row][col + 1] = d + costLeft[row][col];
            pq.push({row, col + 1, dist2[row][col + 1]});
        }

        if (row < r && dist2[row + 1][col] > d + costDown[row][col])
        {
            dist2[row + 1][col] = d + costDown[row][col];
            pq.push({row + 1, col, dist2[row + 1][col]});
        }
    }

    for (int i = 1 ; i <= c ; ++i)
    {
        dist[col][i] = dist2[r][i];
    }
}

void init(int R, int C, int H[5000][200], int V[5000][200]) 
{
    r = R;
    c = C;

    for (int i = 1 ; i <= r ; ++i)
    {
        for (int j = 1 ; j < c ; ++j)
        {
            costLeft[i][j] = H[i - 1][j - 1];
        }
    }

    for (int i = 1 ; i < r ; ++i)
    {
        for (int j = 1 ; j <= c ; ++j)
        {
            costDown[i][j] = V[i - 1][j - 1];
        }
    }

    if (r <= 20 && c <= 20)
    {
        small = true;
        for (int i = 1 ; i <= c ; ++i)
        {
            dijkstra(i);
        }
    }
}

void changeH(int P, int Q, int W)
{
    costLeft[P + 1][Q + 1] = W;
    if (r <= 20 && c <= 20)
    {
        for (int i = 1 ; i <= c ; ++i)
        {
            dijkstra(i);
        }
    }
}

void changeV(int P, int Q, int W) 
{
    costDown[P + 1][Q + 1] = W;
    if (r <= 20 && c <= 20)
    {
        for (int i = 1 ; i <= c ; ++i)
        {
            dijkstra(i);
        }
    }
}

int escape(int V1, int V2)
{
    V1++;
    V2++;
    if (small) return dist[V1][V2];
    dijkstra(V1);
    return dist[V1][V2];
}

컴파일 시 표준 에러 (stderr) 메시지

grader.c: In function 'int main()':
grader.c:15:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   15 |  int res;
      |      ^~~

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