oj.uz

답안 #75772

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
75772 2018-09-11T05:26:28 Z andy627 웜뱃 (IOI13_wombats) C++17
12 / 100
 371 ms 263168 KB 
#include "wombats.h"

#include <stdio.h>
#include <vector>
#include <algorithm>
#define ele (1<<13)
#define INF 1e9
using namespace std;

int n,m;
int h[5000][100],v[5000][100];

int sum[5001][100];
int idx[ele<<1][100][100];

void make_leaf(int w){
    if(idx[w+1][0][0]==-1){
        for(int i=0;i<m;i++){
            for(int j=0;j<m;j++) idx[w+ele][i][j]=abs(sum[w][i]-sum[w][j]);
        }
        return;
    }

    for(int i=0;i<m;i++){
        for(int j=0;j<m;j++) idx[w+ele][i][j]=INF;
    }

    vector<int> vl[100],vr[100];
    vl[m-1].push_back(0); vl[m-1].push_back(m-1);
    vr[m-1].push_back(0); vr[m-1].push_back(m-1);

    for(int g=m-1;g>=0;g--){
        if(g>0) vl[g-1].push_back(0),vr[g-1].push_back(0);

        for(int i=0;i+g<m;i++){
            int mnl=-1,mnr=-1;

            for(int j=vl[g][i];j<=vl[g][i+1];j++){
                if(idx[w+ele][i][i+g]>abs(sum[w][i]-sum[w][j])+v[w][j]+abs(sum[w+1][j]-sum[w+1][i+g])){
                    idx[w+ele][i][i+g]=abs(sum[w][i]-sum[w][j])+v[w][j]+abs(sum[w+1][j]-sum[w+1][i+g]);
                    mnl=j;
                }
            }

            for(int j=vr[g][i];j<=vr[g][i+1];j++){
                if(idx[w+ele][i+g][i]>abs(sum[w][i+g]-sum[w][j])+v[w][j]+abs(sum[w+1][j]-sum[w+1][i])){
                    idx[w+ele][i+g][i]=abs(sum[w][i+g]-sum[w][j])+v[w][j]+abs(sum[w+1][j]-sum[w+1][i]);
                    mnr=j;
                }
            }

            if(g>0) vl[g-1].push_back(mnl),vr[g-1].push_back(mnr);
        }

        if(g>0) vl[g-1].push_back(m-1),vr[g-1].push_back(m-1);
    }
}

void update_(int w){
    int c1=w<<1,c2=w<<1|1;

    if(idx[c2][0][0]==-1){
        for(int i=0;i<m;i++){
            for(int j=0;j<m;j++) idx[w][i][j]=idx[c1][i][j];
        }
        return;
    }

    for(int i=0;i<m;i++){
        for(int j=0;j<m;j++) idx[w][i][j]=INF;
    }

    vector<int> vl[100],vr[100];
    vl[m-1].push_back(0); vl[m-1].push_back(m-1);
    vr[m-1].push_back(0); vr[m-1].push_back(m-1);

    for(int g=m-1;g>=0;g--){
        if(g>0) vl[g-1].push_back(0),vr[g-1].push_back(0);

        for(int i=0;i+g<m;i++){
            int mnl=-1,mnr=-1;

            for(int j=vl[g][i];j<=vl[g][i+1];j++){
                if(idx[w][i][i+g]>idx[c1][i][j]+idx[c2][j][i+g]){
                    idx[w][i][i+g]=idx[c1][i][j]+idx[c2][j][i+g];
                    mnl=j;
                }
            }

            for(int j=vr[g][i];j<=vr[g][i+1];j++){
                if(idx[w][i+g][i]>idx[c1][i+g][j]+idx[c2][j][i]){
                    idx[w][i+g][i]=idx[c1][i+g][j]+idx[c2][j][i];
                    mnr=j;
                }
            }

            if(g>0) vl[g-1].push_back(mnl),vr[g-1].push_back(mnr);
        }

        if(g>0) vl[g-1].push_back(m-1),vr[g-1].push_back(m-1);
    }
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
    n=R; m=C;
    for(int i=0;i<n;i++)
        for(int j=0;j<m-1;j++) h[i][j]=H[i][j];
    for(int i=0;i<n-1;i++)
        for(int j=0;j<m;j++) v[i][j]=V[i][j];

    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++) sum[i][j+1]=sum[i][j]+h[i][j];
    }

    for(int i=0;i<n;i++) make_leaf(i);
    for(int i=n-1;i<ele;i++) idx[i+ele][0][0]=-1;

    for(int i=ele-1;i>0;i--) update_(i);

//    for(int i=1;i<(ele<<1);i++){
//        for(int j=0;j<m;j++){
//            for(int k=0;k<m;k++) printf("%d ",idx[i][j][k]);
//            printf("\n");
//        }
//        printf("\n");
//    }
}

void changeH(int P, int Q, int W) {
    h[P][Q]=W;

    for(int j=0;j<m;j++) sum[P][j+1]=sum[P][j]+h[P][j];

    int idx1=P-1,idx2=P;
    if(P){
        make_leaf(idx1); idx1+=ele;
        for(idx1>>=1;idx1;idx1>>=1) update_(idx1);
    }
    make_leaf(idx2); idx2+=ele;
    for(idx2>>=1;idx2;idx2>>=1) update_(idx2);


    for(P+=ele,P>>=1;P;P>>=1) update_(P);

//    printf("****************************************************************************\n\n");

//    for(int i=1;i<(ele<<1);i++){
//        for(int j=0;j<m;j++){
//            for(int k=0;k<m;k++) printf("%d ",idx[i][j][k]);
//            printf("\n");
//        }
//        printf("\n");
//    }
}

void changeV(int P, int Q, int W) {
    v[P][Q]=W;

    make_leaf(P);
    for(P+=ele;P;P>>=1) update_(P);

//    printf("****************************************************************************\n\n");

//    for(int i=1;i<(ele<<1);i++){
//        for(int j=0;j<m;j++){
//            for(int k=0;k<m;k++) printf("%d ",idx[i][j][k]);
//            printf("\n");
//        }
//        printf("\n");
//    }
}

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

Compilation message

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
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 286 ms 131704 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 49 ms 131704 KB Output is correct
2 Correct 52 ms 131704 KB Output is correct
3 Correct 47 ms 131704 KB Output is correct
4 Correct 112 ms 185616 KB Output is correct
5 Correct 108 ms 185736 KB Output is correct
6 Correct 108 ms 186020 KB Output is correct
7 Correct 110 ms 186020 KB Output is correct
8 Correct 104 ms 186020 KB Output is correct
9 Correct 107 ms 186048 KB Output is correct
10 Correct 102 ms 186048 KB Output is correct
11 Correct 186 ms 188280 KB Output is correct
12 Correct 106 ms 188280 KB Output is correct

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 371 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 329 ms 263168 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 358 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 312 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -