제출 #156760

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
156760		Alexa2001	웜뱃 (IOI13_wombats)	C++17	76 / 100	20069 ms	42348 KiB

wombats

#include "wombats.h"
#include <bits/stdc++.h>

using namespace std;

const int B = 100, Cmax = 205, Rmax = 5005;
const int inf = 1e8;

int N, M, rm;
int h[Rmax][Cmax], v[Rmax][Cmax];


static void min_to(int &x, int y) { if(x > y) x = y ;}

static void rec(int a[], int p)
{
    int i;
    for(i=1; i<M; ++i)
        min_to(a[i], a[i-1] + h[p][i-1]);

    for(i=M-2; i>=0; --i)
        min_to(a[i], a[i+1] + h[p][i]);
}

struct matrix
{
    int a[Cmax][Cmax];

    void combine(matrix &A, matrix &B, int pos)
    {
        int i, j, k;

        for(i=0; i<M; ++i)
            for(j=0; j<M; ++j)
            {
                a[i][j] = inf;
                for(k=0; k<M; ++k)
                    min_to(a[i][j], A.a[i][k] + B.a[k][j] + v[pos][k]);
            }
    }

    void refresh(int bucket)
    {
        int i, j, k;

        for(i=0; i<M; ++i)
        {
            for(j=0; j<M; ++j)
                a[i][j] = (i==j ? 0 : inf);

            for(k = bucket * B; k < (bucket+1) * B && k < N; ++k)
            {
                rec(a[i], k);

                if(k + 1 < min(B * (bucket+1), N))
                    for(j=0; j<M; ++j)
                        a[i][j] += v[k][j];
            }
        }
    }
};


#define left_son (node<<1)
#define right_son ((node<<1)|1)
#define mid ((st+dr)>>1)

namespace aint
{
    matrix a[ (Rmax / B + 3) << 2];

    void update(int node, int st, int dr, int pos)
    {
        if(st == dr)
        {
            a[node].refresh(st);
            return;
        }

        if(pos <= mid) update(left_son, st, mid, pos);
            else update(right_son, mid+1, dr, pos);

        a[node].combine(a[left_son], a[right_son], (mid+1) * B - 1);
    }

    void build(int node, int st, int dr)
    {
        if(st == dr)
        {
            a[node].refresh(st);
            return;
        }

        build(left_son, st, mid);
        build(right_son, mid+1, dr);

        a[node].combine(a[left_son], a[right_son], (mid+1) * B - 1);
    }

    int get_answer(int start, int finish)
    {
        return a[1].a[start][finish];
    }
};


void init(int R, int C, int H[5000][200], int V[5000][200])
{
    N = R; M = C;
    rm = (N-1) / B;

    int i, j;
    for(i=0; i<N; ++i)
        for(j=0; j<M; ++j)
            h[i][j] = H[i][j], v[i][j] = V[i][j];

    aint::build(1, 0, rm);
}

void changeH(int P, int Q, int W)
{
    h[P][Q] = W;
    aint::update(1, 0, rm, P / B);
}

void changeV(int P, int Q, int W)
{
    v[P][Q] = W;
    aint::update(1, 0, rm, P / B);
}

int escape(int V1, int V2)
{
    return aint::get_answer(V1, V2);
}

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

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

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