oj.uz

Submission #1030161

# Submission time Handle Problem Language Result Execution time Memory
1030161 2024-07-21T22:03:14 Z noyancanturk Wombats (IOI13_wombats) C++17
37 / 100
 924 ms 17500 KB 
#include "wombats.h"

#include <bits/stdc++.h>
using namespace std;

int n,c,x;
int h[5000][200],v[5000][200];
using mat=int[200][200];

mat dp[2];
 
void calc(int l,int r){
    for(int i=0;i<c;i++){
        for(int j=0;j<c;j++){
            dp[0][i][j]=2e9;
        }
        dp[0][i][i]=0;
    }
    if(1<c){
        for(int i=1;i<c;i++){
            for(int j=0;j<i;j++){
                dp[0][i][j]=min(dp[0][i][j],dp[0][i-1][j]+h[r][i-1]);
            }
        }
        for(int i=c-2;0<=i;i--){
            for(int j=c-1;i<j;j--){
                dp[0][i][j]=min(dp[0][i][j],dp[0][i+1][j]+h[r][i]);
            }
        }
    }
    x=0;
    for(int i=r-1;l<=i;i--){
        x=!x;
        for(int j=0;j<c;j++){
            for(int k=0;k<c;k++){
                dp[x][j][k]=dp[!x][j][k]+v[i][j];
            }
        }
        if(1<c){
            for(int j=1;j<c;j++){
                for(int k=0;k<c;k++){
                    dp[x][j][k]=min(dp[x][j][k],dp[x][j-1][k]+h[i][j-1]);
                }
            }
            for(int j=c-2;0<=j;j--){
                for(int k=0;k<c;k++){
                    dp[x][j][k]=min(dp[x][j][k],dp[x][j+1][k]+h[i][j]);
                }
            }
        }
    }
}

struct{
    mat tree[800];
    #define cur tree[node]
    void build(int l,int r,int node){
        if(r-l<50){    
            calc(l,r+1);
            for(int i=0;i<c;i++){
                for(int j=0;j<c;j++){
                    cur[i][j]=dp[x][i][j];
                }
            }
            return;
        }
        int mid=(l+r)>>1,child=node<<1;
        build(l,mid,child),build(mid+1,r,child|1);
        for(int i=0;i<c;i++){
            for(int j=0;j<c;j++){
                cur[i][j]=INT_MAX;
                for(int k=0;k<c;k++){
                    cur[i][j]=min(cur[i][j],tree[child][i][k]+tree[child|1][k][j]);
                }
            }
        }
    }
    int P;
    void update(int l,int r,int node){
        if(r-l<50){    
            calc(l,r+1);
            for(int i=0;i<c;i++){
                for(int j=0;j<c;j++){
                    cur[i][j]=dp[x][i][j];
                }
            }
            return;
        }
        int mid=(l+r)>>1,child=node<<1;
        if(P<=mid)update(l,mid,child);
        else update(mid+1,r,child|1);
        for(int i=0;i<c;i++){
            for(int j=0;j<c;j++){
                cur[i][j]=INT_MAX;
                for(int k=0;k<c;k++){
                    cur[i][j]=min(cur[i][j],tree[child][i][k]+tree[child|1][k][j]);
                }
            }
        }
    }
    void update(int p){
        P=p;
        update(0,n-2,1);
    }
}st;

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

void changeH(int P, int Q, int W) {
    h[P][Q]=W;
    st.update(P);
}

void changeV(int P, int Q, int W) {
    v[P][Q]=W;
    st.update(P);
}

int escape(int V1, int V2) {
    return st.tree[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]
   15 |  int res;
      |      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 13144 KB Output is correct
2 Correct 8 ms 13148 KB Output is correct
3 Correct 42 ms 15996 KB Output is correct
4 Correct 6 ms 13144 KB Output is correct
5 Correct 6 ms 13148 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 344 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 39 ms 2940 KB Output is correct
12 Correct 1 ms 344 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 183 ms 1112 KB Output is correct
2 Correct 180 ms 1244 KB Output is correct
3 Correct 186 ms 1112 KB Output is correct
4 Correct 195 ms 1244 KB Output is correct
5 Correct 205 ms 1264 KB Output is correct
6 Correct 0 ms 448 KB Output is correct
7 Correct 1 ms 344 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 924 ms 1256 KB Output is correct
10 Correct 1 ms 600 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 7 ms 17496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 220 ms 1260 KB Output is correct
2 Correct 190 ms 1112 KB Output is correct
3 Correct 185 ms 1364 KB Output is correct
4 Correct 219 ms 1368 KB Output is correct
5 Correct 181 ms 1116 KB Output is correct
6 Incorrect 10 ms 17500 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 191 ms 1116 KB Output is correct
2 Correct 161 ms 1116 KB Output is correct
3 Correct 161 ms 1112 KB Output is correct
4 Correct 160 ms 1116 KB Output is correct
5 Correct 202 ms 1116 KB Output is correct
6 Incorrect 7 ms 17500 KB Output isn't correct
7 Halted 0 ms 0 KB -