oj.uz

Submission #1021274

# Submission time Handle Problem Language Result Execution time Memory
1021274 2024-07-12T16:35:11 Z amirhoseinfar1385 Wombats (IOI13_wombats) C++17
100 / 100
 3386 ms 158800 KB 
#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=5000+10,maxm=200+10,t=20,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 48 ms 100304 KB Output is correct
2 Correct 52 ms 100288 KB Output is correct
3 Correct 80 ms 103248 KB Output is correct
4 Correct 42 ms 100444 KB Output is correct
5 Correct 42 ms 100320 KB Output is correct
6 Correct 37 ms 90192 KB Output is correct
7 Correct 37 ms 90132 KB Output is correct
8 Correct 37 ms 90232 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 90196 KB Output is correct
2 Correct 46 ms 90072 KB Output is correct
3 Correct 38 ms 90196 KB Output is correct
4 Correct 38 ms 90312 KB Output is correct
5 Correct 38 ms 90196 KB Output is correct
6 Correct 36 ms 90204 KB Output is correct
7 Correct 37 ms 90196 KB Output is correct
8 Correct 38 ms 90196 KB Output is correct
9 Correct 38 ms 90196 KB Output is correct
10 Correct 44 ms 90200 KB Output is correct
11 Correct 75 ms 92500 KB Output is correct
12 Correct 38 ms 90200 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 104 ms 91216 KB Output is correct
2 Correct 109 ms 91140 KB Output is correct
3 Correct 110 ms 91216 KB Output is correct
4 Correct 123 ms 91216 KB Output is correct
5 Correct 137 ms 90964 KB Output is correct
6 Correct 40 ms 90192 KB Output is correct
7 Correct 47 ms 90212 KB Output is correct
8 Correct 38 ms 90196 KB Output is correct
9 Correct 391 ms 91208 KB Output is correct
10 Correct 38 ms 90196 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 108400 KB Output is correct
2 Correct 52 ms 108544 KB Output is correct
3 Correct 48 ms 108452 KB Output is correct
4 Correct 65 ms 109908 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 90964 KB Output is correct
2 Correct 133 ms 90964 KB Output is correct
3 Correct 111 ms 90964 KB Output is correct
4 Correct 111 ms 91216 KB Output is correct
5 Correct 111 ms 90960 KB Output is correct
6 Correct 46 ms 108368 KB Output is correct
7 Correct 46 ms 108372 KB Output is correct
8 Correct 47 ms 108376 KB Output is correct
9 Correct 65 ms 109904 KB Output is correct
10 Correct 42 ms 100436 KB Output is correct
11 Correct 43 ms 100432 KB Output is correct
12 Correct 79 ms 103088 KB Output is correct
13 Correct 42 ms 100432 KB Output is correct
14 Correct 46 ms 100440 KB Output is correct
15 Correct 49 ms 90196 KB Output is correct
16 Correct 38 ms 90204 KB Output is correct
17 Correct 38 ms 90188 KB Output is correct
18 Correct 49 ms 90192 KB Output is correct
19 Correct 38 ms 90200 KB Output is correct
20 Correct 38 ms 90204 KB Output is correct
21 Correct 38 ms 90196 KB Output is correct
22 Correct 37 ms 90276 KB Output is correct
23 Correct 37 ms 90168 KB Output is correct
24 Correct 37 ms 90204 KB Output is correct
25 Correct 75 ms 92588 KB Output is correct
26 Correct 50 ms 90196 KB Output is correct
27 Correct 389 ms 91224 KB Output is correct
28 Correct 834 ms 132432 KB Output is correct
29 Correct 822 ms 125524 KB Output is correct
30 Correct 801 ms 125268 KB Output is correct
31 Correct 873 ms 133832 KB Output is correct
32 Correct 38 ms 90196 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 91216 KB Output is correct
2 Correct 109 ms 91192 KB Output is correct
3 Correct 114 ms 91220 KB Output is correct
4 Correct 110 ms 91008 KB Output is correct
5 Correct 113 ms 91208 KB Output is correct
6 Correct 50 ms 108468 KB Output is correct
7 Correct 46 ms 108372 KB Output is correct
8 Correct 46 ms 108372 KB Output is correct
9 Correct 72 ms 109904 KB Output is correct
10 Correct 43 ms 100432 KB Output is correct
11 Correct 42 ms 100432 KB Output is correct
12 Correct 81 ms 103248 KB Output is correct
13 Correct 43 ms 100436 KB Output is correct
14 Correct 43 ms 100368 KB Output is correct
15 Correct 999 ms 157456 KB Output is correct
16 Correct 3386 ms 158800 KB Output is correct
17 Correct 38 ms 90196 KB Output is correct
18 Correct 37 ms 90144 KB Output is correct
19 Correct 37 ms 90204 KB Output is correct
20 Correct 38 ms 90196 KB Output is correct
21 Correct 38 ms 90196 KB Output is correct
22 Correct 38 ms 90204 KB Output is correct
23 Correct 37 ms 90196 KB Output is correct
24 Correct 37 ms 90204 KB Output is correct
25 Correct 52 ms 90192 KB Output is correct
26 Correct 38 ms 90364 KB Output is correct
27 Correct 84 ms 92672 KB Output is correct
28 Correct 38 ms 90192 KB Output is correct
29 Correct 381 ms 91228 KB Output is correct
30 Correct 799 ms 132436 KB Output is correct
31 Correct 2979 ms 156632 KB Output is correct
32 Correct 3186 ms 156612 KB Output is correct
33 Correct 785 ms 125448 KB Output is correct
34 Correct 3106 ms 145824 KB Output is correct
35 Correct 804 ms 125268 KB Output is correct
36 Correct 3204 ms 145916 KB Output is correct
37 Correct 835 ms 133812 KB Output is correct
38 Correct 3066 ms 155868 KB Output is correct
39 Correct 38 ms 90268 KB Output is correct
40 Correct 3260 ms 143752 KB Output is correct