oj.uz

답안 #76044

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

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

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

int sum[5001][101];
int idx[ele<<1][20][20];

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[c1][0][0]==-1){
        idx[w][0][0]=-1;
        return;
    }
    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-1;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);

//    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); P+=ele;
    for(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");
//    }
}

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 Correct 50 ms 33784 KB Output is correct
2 Incorrect 48 ms 33928 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 33928 KB Output is correct
2 Correct 21 ms 33928 KB Output is correct
3 Correct 21 ms 33928 KB Output is correct
4 Correct 73 ms 33928 KB Output is correct
5 Correct 23 ms 33928 KB Output is correct
6 Correct 21 ms 33928 KB Output is correct
7 Correct 22 ms 33928 KB Output is correct
8 Correct 22 ms 33928 KB Output is correct
9 Correct 22 ms 33928 KB Output is correct
10 Correct 22 ms 33928 KB Output is correct
11 Correct 157 ms 33928 KB Output is correct
12 Correct 22 ms 33928 KB Output is correct

Subtask #3
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 535 ms 33928 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 60 ms 41560 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 543 ms 41560 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 536 ms 41560 KB Output isn't correct
2 Halted 0 ms 0 KB -