oj.uz

Submission #1012803

# Submission time Handle Problem Language Result Execution time Memory
1012803 2024-07-02T15:56:11 Z ttamx Wombats (IOI13_wombats) C++17
100 / 100
 3044 ms 196536 KB 
#include "wombats.h"
#include <bits/stdc++.h>

using namespace std;

const int N=5005;
const int M=205;
const int B=10;
const int K=1<<10;
const int INF=1e9;

int n,m,b;
int h[N][M],v[N][M];

struct Matrix:array<array<int,M>,M>{
    Matrix(){
        for(int i=0;i<M;i++)for(int j=0;j<M;j++)(*this)[i][j]=INF;
        for(int i=0;i<M;i++)(*this)[i][i]=0;
    }
    friend Matrix operator*(const Matrix &a,const Matrix &b){
        Matrix res;
        array<array<int,M>,M> opt;
        for(int i=1;i<=m;i++)opt[i][0]=1;
        for(int i=1;i<=m;i++)opt[m+1][i]=m;
        for(int i=m;i>=1;i--){
            for(int j=1;j<=m;j++){
                res[i][j]=INF;
                for(int k=opt[i][j-1];k<=opt[i+1][j];k++){
                    int val=a[i][k]+b[k][j];
                    if(val<res[i][j]){
                        res[i][j]=val;
                        opt[i][j]=k;
                    }
                }
            }
        }
        return res;
    }
};

Matrix get_one(int x){
    Matrix res;
    for(int i=1;i<=m;i++){
        res[i][i]=0;
        for(int j=i+1;j<=m;j++){
            res[i][j]=res[i][j-1]+h[x][j-1];
        }
        for(int j=i-1;j>=1;j--){
            res[i][j]=res[i][j+1]+h[x][j];
        }
    }
    for(int i=1;i<=m;i++){
        for(int j=1;j<=m;j++){
            res[i][j]+=v[x][j];
        }
    }
    return res;
}

Matrix get_range(int x){
    int l=(x-1)*B+1,r=min(x*B,n);
    Matrix res=get_one(l);
    for(int i=l+1;i<=r;i++)res=res*get_one(i);
    return res;
}

struct SegTree{
    Matrix t[K];
    void build(int l,int r,int i){
        if(l==r)return void(t[i]=get_range(l));
        int m=(l+r)/2;
        build(l,m,i*2);
        build(m+1,r,i*2+1);
        t[i]=t[i*2]*t[i*2+1];
    }
    void build(){
        build(1,b,1);
    }
    void update(int l,int r,int i,int x){
        if(l==r)return void(t[i]=get_range(x));
        int m=(l+r)/2;
        if(x<=m)update(l,m,i*2,x);
        else update(m+1,r,i*2+1,x);
        t[i]=t[i*2]*t[i*2+1];
    }
    void update(int x){
        update(1,b,1,x);
    }
}s;

void init(int _n,int _m,int _h[5000][200],int _v[5000][200]){
    n=_n,m=_m,b=(n-1)/B+1;
    for(int i=1;i<=n;i++)for(int j=1;j<=m-1;j++)h[i][j]=_h[i-1][j-1];
    for(int i=1;i<=n-1;i++)for(int j=1;j<=m;j++)v[i][j]=_v[i-1][j-1];
    s.build();
}

void changeH(int i,int j,int x){
    h[i+1][j+1]=x;
    s.update(i/B+1);
}

void changeV(int i,int j,int x){
    v[i+1][j+1]=x;
    s.update(i/B+1);
}

int escape(int i,int j){
    return s.t[1][i+1][j+1];
}

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 754 ms 179444 KB Output is correct
2 Correct 707 ms 179544 KB Output is correct
3 Correct 744 ms 182216 KB Output is correct
4 Correct 694 ms 179460 KB Output is correct
5 Correct 727 ms 179440 KB Output is correct
6 Correct 74 ms 170832 KB Output is correct
7 Correct 70 ms 170856 KB Output is correct
8 Correct 63 ms 170832 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 170828 KB Output is correct
2 Correct 60 ms 170832 KB Output is correct
3 Correct 59 ms 170832 KB Output is correct
4 Correct 66 ms 170892 KB Output is correct
5 Correct 59 ms 171052 KB Output is correct
6 Correct 63 ms 171088 KB Output is correct
7 Correct 65 ms 171088 KB Output is correct
8 Correct 64 ms 171040 KB Output is correct
9 Correct 62 ms 171068 KB Output is correct
10 Correct 84 ms 171088 KB Output is correct
11 Correct 105 ms 173396 KB Output is correct
12 Correct 60 ms 171088 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 189 ms 171352 KB Output is correct
2 Correct 229 ms 171532 KB Output is correct
3 Correct 203 ms 171468 KB Output is correct
4 Correct 229 ms 171344 KB Output is correct
5 Correct 221 ms 171348 KB Output is correct
6 Correct 65 ms 170800 KB Output is correct
7 Correct 81 ms 170760 KB Output is correct
8 Correct 65 ms 170872 KB Output is correct
9 Correct 691 ms 171344 KB Output is correct
10 Correct 68 ms 170832 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 790 ms 185860 KB Output is correct
2 Correct 753 ms 185936 KB Output is correct
3 Correct 776 ms 185680 KB Output is correct
4 Correct 834 ms 187200 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 216 ms 171524 KB Output is correct
2 Correct 190 ms 171388 KB Output is correct
3 Correct 209 ms 171348 KB Output is correct
4 Correct 212 ms 171348 KB Output is correct
5 Correct 204 ms 171344 KB Output is correct
6 Correct 747 ms 185680 KB Output is correct
7 Correct 910 ms 185936 KB Output is correct
8 Correct 745 ms 185680 KB Output is correct
9 Correct 783 ms 187220 KB Output is correct
10 Correct 704 ms 179284 KB Output is correct
11 Correct 675 ms 179280 KB Output is correct
12 Correct 732 ms 182100 KB Output is correct
13 Correct 719 ms 179540 KB Output is correct
14 Correct 670 ms 179280 KB Output is correct
15 Correct 57 ms 170832 KB Output is correct
16 Correct 60 ms 170796 KB Output is correct
17 Correct 71 ms 170828 KB Output is correct
18 Correct 61 ms 171092 KB Output is correct
19 Correct 61 ms 171092 KB Output is correct
20 Correct 61 ms 171088 KB Output is correct
21 Correct 61 ms 170876 KB Output is correct
22 Correct 64 ms 171092 KB Output is correct
23 Correct 64 ms 171092 KB Output is correct
24 Correct 65 ms 170868 KB Output is correct
25 Correct 98 ms 173416 KB Output is correct
26 Correct 60 ms 171088 KB Output is correct
27 Correct 608 ms 171364 KB Output is correct
28 Correct 1229 ms 189776 KB Output is correct
29 Correct 1331 ms 187688 KB Output is correct
30 Correct 1251 ms 187476 KB Output is correct
31 Correct 1276 ms 191572 KB Output is correct
32 Correct 59 ms 170832 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 171492 KB Output is correct
2 Correct 180 ms 171344 KB Output is correct
3 Correct 194 ms 171344 KB Output is correct
4 Correct 187 ms 171348 KB Output is correct
5 Correct 204 ms 171344 KB Output is correct
6 Correct 704 ms 185680 KB Output is correct
7 Correct 691 ms 185684 KB Output is correct
8 Correct 699 ms 186056 KB Output is correct
9 Correct 749 ms 187216 KB Output is correct
10 Correct 686 ms 179280 KB Output is correct
11 Correct 698 ms 179280 KB Output is correct
12 Correct 727 ms 182096 KB Output is correct
13 Correct 739 ms 179216 KB Output is correct
14 Correct 701 ms 179540 KB Output is correct
15 Correct 1199 ms 195324 KB Output is correct
16 Correct 3044 ms 196536 KB Output is correct
17 Correct 63 ms 170832 KB Output is correct
18 Correct 62 ms 170892 KB Output is correct
19 Correct 62 ms 170836 KB Output is correct
20 Correct 62 ms 171088 KB Output is correct
21 Correct 62 ms 171092 KB Output is correct
22 Correct 67 ms 171092 KB Output is correct
23 Correct 63 ms 171088 KB Output is correct
24 Correct 61 ms 171088 KB Output is correct
25 Correct 61 ms 170976 KB Output is correct
26 Correct 63 ms 171092 KB Output is correct
27 Correct 108 ms 173376 KB Output is correct
28 Correct 62 ms 170920 KB Output is correct
29 Correct 601 ms 171348 KB Output is correct
30 Correct 1305 ms 189800 KB Output is correct
31 Correct 2797 ms 194172 KB Output is correct
32 Correct 2775 ms 194012 KB Output is correct
33 Correct 1323 ms 187484 KB Output is correct
34 Correct 2875 ms 191448 KB Output is correct
35 Correct 1251 ms 187528 KB Output is correct
36 Correct 2872 ms 191312 KB Output is correct
37 Correct 1297 ms 191568 KB Output is correct
38 Correct 2793 ms 194624 KB Output is correct
39 Correct 60 ms 170832 KB Output is correct
40 Correct 2904 ms 191444 KB Output is correct