oj.uz

답안 #75777

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
75777 2018-09-11T05:34:09 Z andy627 웜뱃 (IOI13_wombats) C++17
12 / 100
 385 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][101];
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 291 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 53 ms 131704 KB Output is correct
2 Correct 51 ms 131704 KB Output is correct
3 Correct 51 ms 131704 KB Output is correct
4 Correct 111 ms 185660 KB Output is correct
5 Correct 112 ms 185740 KB Output is correct
6 Correct 110 ms 185748 KB Output is correct
7 Correct 110 ms 185860 KB Output is correct
8 Correct 108 ms 185860 KB Output is correct
9 Correct 107 ms 186000 KB Output is correct
10 Correct 107 ms 186000 KB Output is correct
11 Correct 190 ms 188212 KB Output is correct
12 Correct 114 ms 188212 KB Output is correct

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 385 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 343 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 376 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 322 ms 263168 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -