제출 #1036417

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1036417		hmm789	웜뱃 (IOI13_wombats)	C++14	100 / 100	2410 ms	110488 KiB

wombats

#include <bits/stdc++.h>
#include "wombats.h"
using namespace std;
#define INF 2000000000
 
const int B = 20;
 
int h[5000][200], v[5000][200], bl[5000], br[5000], pos[5000], r, c;
 
struct node {
    int s, e, m;
    vector<vector<int>> f;
    node *l, *r;
    node(int _s, int _e) {
        s = _s, e = _e, m = (s+e)/2;
        for(int i = 0; i < 200; i++) {
            vector<int> v(200);
            f.push_back(v);
        }
        if(s != e) {
            l = new node(s, m);
            r = new node(m+1, e);
            merge(l->f, r->f, f);
        } else {
            build(s);
        }
    }
    void build(int s) {
        for(int i = 0; i < c; i++) {
            for(int j = i, res = 0; j < c; j++, res += h[bl[s]][j-1]) f[i][j] = res;
            for(int j = i, res = 0; j >= 0; j--, res += h[bl[s]][j]) f[i][j] = res;
            for(int j = 0; j < c; j++) f[i][j] += v[bl[s]][j];
            for(int k = bl[s]+1; k <= br[s]; k++) {
                for(int j = 1; j < c; j++) f[i][j] = min(f[i][j], f[i][j-1] + h[k][j-1]);
                for(int j = c-2; j >= 0; j--) f[i][j] = min(f[i][j], f[i][j+1] + h[k][j]);
                for(int j = 0; j < c; j++) f[i][j] += v[k][j];
            }
        }
    }
    void merge(vector<vector<int>> &a, vector<vector<int>> &b, vector<vector<int>> &f) {
        for(int i = 0; i < c; i++) for(int j = 0; j < c; j++) f[i][j] = INF;
        int p[c][c];
        memset(p, -1, sizeof(p));
        for(int i = 0; i < c; i++) {
            for(int j = c-1; j >= 0; j--) {
                int st = (i && p[i-1][j] != -1 ? p[i-1][j] : 0);
                int ed = (j != c-1 && p[i][j+1] != -1 ? p[i][j+1] : c-1);
                for(int k = st; k <= ed; k++) if(f[i][j] > a[i][k] + b[k][j]) {
                    f[i][j] = a[i][k] + b[k][j];
                    p[i][j] = k;
                }
            }
        }
    }
    void update(int x) {
        if(s == e) {build(s); return;}
        else if(x > m) r->update(x);
        else l->update(x);
        merge(l->f, r->f, f);
    }
} *root;
 
void init(int R, int C, int H[5000][200], int V[5000][200]) {
    r = R; c = C;
    for(int i = 0; i < r; i++) for(int j = 0; j < c-1; j++) h[i][j] = H[i][j];
    for(int i = 0; i < r-1; i++) for(int j = 0; j < c; j++) v[i][j] = V[i][j];
    int cnt = (r-1)/B + 1;
    for(int i = 0; i < cnt; i++) {
        bl[i] = i*B;
        br[i] = min((i+1)*B-1, r-1);
    }
    for(int i = 0; i < cnt; i++) {
        for(int j = bl[i]; j <= br[i]; j++) pos[j] = i;
    }
    root = new node(0, cnt-1);
}
 
void changeH(int P, int Q, int W) {
    h[P][Q] = W;
    root->update(pos[P]);
}
 
void changeV(int P, int Q, int W) {
    v[P][Q] = W;
    root->update(pos[P]);
}
 
int escape(int V1, int V2) {
    return root->f[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: 18 / 18
• Subtask 5: 21 / 21
• Subtask 6: 24 / 24