oj.uz

Submission #1021272

# Submission time Handle Problem Language Result Execution time Memory
1021272 2024-07-12T16:34:02 Z amirhoseinfar1385 Wombats (IOI13_wombats) C++17
100 / 100
 3557 ms 141092 KB 
#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=5000+10,maxm=200+10,t=35,mt=(maxn/t)+5,lg=log2(mt)+1;
int n,m,inf=1e9+5;
struct bakhsh{
    int allr[t+5][maxm],allc[t+5][maxm],dp[maxm][maxm],ps[maxm],suf[maxm],mxr=0;
    void calps(int i){
        for(int j=1;j<=m;j++){
            ps[j]=ps[j-1]+allr[i][j-1];
        }
    }
    void calc(){
        for(int k=1;k<=m;k++){
            calps(0);
            for(int j=1;j<=m;j++){
                dp[k][j]=abs(ps[k]-ps[j]);
            }
            for(int i=1;i<=mxr;i++){
                int mn=inf;
                for(int j=1;j<=m;j++){
                    mn=min(mn+allr[i][j-1],dp[k][j]+allc[i-1][j]);
                    ps[j]=mn;
                }
                mn=inf;
                for(int j=m;j>=1;j--){
                    mn=min(mn+allr[i][j],dp[k][j]+allc[i-1][j]);
                    dp[k][j]=min(ps[j],mn);
                }
            }
            for(int j=1;j<=m;j++){
                dp[k][j]+=allc[mxr][j];
            }
        }
    }
    void updr(int i,int j,int w){
        j++;
        mxr=max(mxr,i);
        allr[i][j]=w;
    }
    void updc(int i,int j,int w){
        j++;
        mxr=max(mxr,i);
        allc[i][j]=w;
    }
}allsq[mt];
int kaf=(1<<lg);

struct segment{
    int seg[(1<<(lg+1))][maxm][maxm];
    int now[maxm][maxm];
    segment(){
        for(int i=0;i<(1<<lg+1);i++){
            for(int r=0;r<maxm;r++){
                for(int c=0;c<maxm;c++){
                    seg[i][r][c]=inf;
                }
            }
        }
    }
    pair<int,int>stf[maxm][maxm];
    void por(int ind,int ez[maxm][maxm]){
        for(int i=1;i<=m;i++){
            for(int j=1;j<=m;j++){
                seg[ind][i][j]=ez[i][j];
            }
        }
    }
    void dfs(int cl,int cr,int r=m,int c=1){
        if(r==0||c==m+1){
            return ;
        }
    //    cout<<cl<<" "<<cr<<" "<<r<<" "<<c<<endl;
        if(r==m){
            stf[r][c].second=m;
        }
        if(c==1){
            stf[r][c].first=1;
        }
        now[r][c]=inf;
        int opt=stf[r][c].first;
        for(int i=stf[r][c].first;i<=stf[r][c].second;i++){
            if(seg[cl][r][i]+seg[cr][i][c]<now[r][c]){
                opt=i;
                now[r][c]=seg[cl][r][i]+seg[cr][i][c];
            }
        }
        stf[r-1][c].second=opt;
        stf[r][c+1].first=opt;
        dfs(cl,cr,r-1,c);
        if(r==m){
            dfs(cl,cr,r,c+1);
        }
    }

    void calc(int i){
        if(seg[(i<<1)][1][1]==inf){
            por(i,seg[(i<<1)^1]);
            return ;
        }
        if(seg[(i<<1)^1][1][1]==inf){
            por(i,seg[(i<<1)]);
            return ;
        }
        dfs((i<<1),(i<<1)^1);
        por(i,now);
    }

    void upd(int i,int dp[maxm][maxm]){
        i+=kaf;
        por(i,dp);
        i>>=1;
        while(i>0){
            calc(i);
            i>>=1;
        }
    }
}seg;


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++){
            allsq[i/t].updr(i%t,j,H[i][j]);
        }
    }
    for(int i=0;i<n-1;i++){
        for(int j=0;j<m;j++){
            allsq[i/t].updc(i%t,j,V[i][j]);
        }
    }
    for(int i=0;i<=(n-1)/t;i++){
        allsq[i].calc();
        seg.upd(i,allsq[i].dp);
    }
}
 
void changeH( int P, int Q, int W) {
    allsq[P/t].updr(P%t,Q,W);
    allsq[P/t].calc();
    seg.upd(P/t,allsq[P/t].dp);
}
 
void changeV( int P, int Q, int W) {
    allsq[P/t].updc(P%t,Q,W);
    allsq[P/t].calc();
    seg.upd(P/t,allsq[P/t].dp);
}
 
int escape( int V1, int V2) {
    V1++;
    V2++;
    return seg.seg[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;
      |      ^~~
wombats.cpp: In constructor 'segment::segment()':
wombats.cpp:53:29: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   53 |         for(int i=0;i<(1<<lg+1);i++){
      |                           ~~^~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 98880 KB Output is correct
2 Correct 44 ms 98896 KB Output is correct
3 Correct 114 ms 101716 KB Output is correct
4 Correct 44 ms 99020 KB Output is correct
5 Correct 43 ms 98900 KB Output is correct
6 Correct 38 ms 89580 KB Output is correct
7 Correct 38 ms 89684 KB Output is correct
8 Correct 38 ms 89688 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 89680 KB Output is correct
2 Correct 38 ms 89688 KB Output is correct
3 Correct 39 ms 89608 KB Output is correct
4 Correct 38 ms 89824 KB Output is correct
5 Correct 38 ms 89680 KB Output is correct
6 Correct 41 ms 89684 KB Output is correct
7 Correct 38 ms 89696 KB Output is correct
8 Correct 38 ms 89704 KB Output is correct
9 Correct 38 ms 89684 KB Output is correct
10 Correct 38 ms 89684 KB Output is correct
11 Correct 77 ms 92064 KB Output is correct
12 Correct 40 ms 89684 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 90340 KB Output is correct
2 Correct 128 ms 90544 KB Output is correct
3 Correct 128 ms 90444 KB Output is correct
4 Correct 146 ms 90448 KB Output is correct
5 Correct 129 ms 90556 KB Output is correct
6 Correct 38 ms 89684 KB Output is correct
7 Correct 37 ms 89828 KB Output is correct
8 Correct 37 ms 89760 KB Output is correct
9 Correct 524 ms 90452 KB Output is correct
10 Correct 48 ms 89748 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 107156 KB Output is correct
2 Correct 45 ms 107088 KB Output is correct
3 Correct 46 ms 107088 KB Output is correct
4 Correct 65 ms 108312 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 90556 KB Output is correct
2 Correct 143 ms 90548 KB Output is correct
3 Correct 150 ms 90556 KB Output is correct
4 Correct 139 ms 90324 KB Output is correct
5 Correct 138 ms 90448 KB Output is correct
6 Correct 46 ms 107092 KB Output is correct
7 Correct 45 ms 106952 KB Output is correct
8 Correct 59 ms 107088 KB Output is correct
9 Correct 72 ms 108468 KB Output is correct
10 Correct 42 ms 99004 KB Output is correct
11 Correct 43 ms 98896 KB Output is correct
12 Correct 79 ms 101868 KB Output is correct
13 Correct 42 ms 98900 KB Output is correct
14 Correct 43 ms 98900 KB Output is correct
15 Correct 37 ms 89680 KB Output is correct
16 Correct 38 ms 89680 KB Output is correct
17 Correct 38 ms 89688 KB Output is correct
18 Correct 37 ms 89692 KB Output is correct
19 Correct 38 ms 89784 KB Output is correct
20 Correct 38 ms 89836 KB Output is correct
21 Correct 43 ms 89660 KB Output is correct
22 Correct 37 ms 89680 KB Output is correct
23 Correct 37 ms 89684 KB Output is correct
24 Correct 36 ms 89792 KB Output is correct
25 Correct 93 ms 92120 KB Output is correct
26 Correct 38 ms 89688 KB Output is correct
27 Correct 484 ms 90476 KB Output is correct
28 Correct 843 ms 122580 KB Output is correct
29 Correct 866 ms 117408 KB Output is correct
30 Correct 930 ms 117348 KB Output is correct
31 Correct 930 ms 124364 KB Output is correct
32 Correct 44 ms 89672 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 112 ms 90460 KB Output is correct
2 Correct 161 ms 90364 KB Output is correct
3 Correct 133 ms 90452 KB Output is correct
4 Correct 130 ms 90472 KB Output is correct
5 Correct 130 ms 90452 KB Output is correct
6 Correct 46 ms 107088 KB Output is correct
7 Correct 46 ms 107088 KB Output is correct
8 Correct 46 ms 107088 KB Output is correct
9 Correct 70 ms 108424 KB Output is correct
10 Correct 42 ms 98992 KB Output is correct
11 Correct 46 ms 99048 KB Output is correct
12 Correct 81 ms 101716 KB Output is correct
13 Correct 43 ms 98900 KB Output is correct
14 Correct 42 ms 98896 KB Output is correct
15 Correct 817 ms 139604 KB Output is correct
16 Correct 3557 ms 141092 KB Output is correct
17 Correct 42 ms 89656 KB Output is correct
18 Correct 38 ms 89684 KB Output is correct
19 Correct 37 ms 89604 KB Output is correct
20 Correct 39 ms 89824 KB Output is correct
21 Correct 38 ms 89684 KB Output is correct
22 Correct 38 ms 89680 KB Output is correct
23 Correct 38 ms 89692 KB Output is correct
24 Correct 38 ms 89744 KB Output is correct
25 Correct 37 ms 89680 KB Output is correct
26 Correct 40 ms 89684 KB Output is correct
27 Correct 112 ms 92192 KB Output is correct
28 Correct 39 ms 89684 KB Output is correct
29 Correct 485 ms 90452 KB Output is correct
30 Correct 839 ms 122708 KB Output is correct
31 Correct 3230 ms 138620 KB Output is correct
32 Correct 3470 ms 138476 KB Output is correct
33 Correct 901 ms 117332 KB Output is correct
34 Correct 3283 ms 129660 KB Output is correct
35 Correct 865 ms 117080 KB Output is correct
36 Correct 3476 ms 129780 KB Output is correct
37 Correct 936 ms 123984 KB Output is correct
38 Correct 3512 ms 138252 KB Output is correct
39 Correct 38 ms 89684 KB Output is correct
40 Correct 3377 ms 130968 KB Output is correct