oj.uz

Submission #1021264

# Submission time Handle Problem Language Result Execution time Memory
1021264 2024-07-12T16:32:14 Z amirhoseinfar1385 Wombats (IOI13_wombats) C++17
100 / 100
 5178 ms 84836 KB 
#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=5000+10,maxm=200+10,t=70,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 29 ms 68688 KB Output is correct
2 Correct 26 ms 68952 KB Output is correct
3 Correct 63 ms 71524 KB Output is correct
4 Correct 24 ms 68956 KB Output is correct
5 Correct 24 ms 68692 KB Output is correct
6 Correct 20 ms 66652 KB Output is correct
7 Correct 21 ms 64604 KB Output is correct
8 Correct 20 ms 64484 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 66652 KB Output is correct
2 Correct 23 ms 64596 KB Output is correct
3 Correct 24 ms 66652 KB Output is correct
4 Correct 23 ms 64592 KB Output is correct
5 Correct 23 ms 64592 KB Output is correct
6 Correct 24 ms 64604 KB Output is correct
7 Correct 24 ms 64600 KB Output is correct
8 Correct 29 ms 66524 KB Output is correct
9 Correct 25 ms 64604 KB Output is correct
10 Correct 21 ms 66648 KB Output is correct
11 Correct 64 ms 66800 KB Output is correct
12 Correct 21 ms 64600 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 64852 KB Output is correct
2 Correct 183 ms 66648 KB Output is correct
3 Correct 164 ms 64884 KB Output is correct
4 Correct 151 ms 64852 KB Output is correct
5 Correct 182 ms 65108 KB Output is correct
6 Correct 21 ms 66648 KB Output is correct
7 Correct 23 ms 64520 KB Output is correct
8 Correct 21 ms 66664 KB Output is correct
9 Correct 814 ms 64664 KB Output is correct
10 Correct 21 ms 66648 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 73048 KB Output is correct
2 Correct 29 ms 74328 KB Output is correct
3 Correct 30 ms 73044 KB Output is correct
4 Correct 48 ms 74580 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 66900 KB Output is correct
2 Correct 178 ms 66872 KB Output is correct
3 Correct 169 ms 66904 KB Output is correct
4 Correct 154 ms 65108 KB Output is correct
5 Correct 179 ms 64852 KB Output is correct
6 Correct 33 ms 74320 KB Output is correct
7 Correct 36 ms 73052 KB Output is correct
8 Correct 31 ms 73156 KB Output is correct
9 Correct 50 ms 74576 KB Output is correct
10 Correct 27 ms 65628 KB Output is correct
11 Correct 26 ms 53848 KB Output is correct
12 Correct 63 ms 56672 KB Output is correct
13 Correct 26 ms 53840 KB Output is correct
14 Correct 31 ms 53784 KB Output is correct
15 Correct 22 ms 45148 KB Output is correct
16 Correct 20 ms 45148 KB Output is correct
17 Correct 30 ms 45076 KB Output is correct
18 Correct 30 ms 45404 KB Output is correct
19 Correct 21 ms 45188 KB Output is correct
20 Correct 22 ms 45400 KB Output is correct
21 Correct 21 ms 45404 KB Output is correct
22 Correct 22 ms 45404 KB Output is correct
23 Correct 30 ms 45400 KB Output is correct
24 Correct 23 ms 45344 KB Output is correct
25 Correct 62 ms 47728 KB Output is correct
26 Correct 23 ms 45400 KB Output is correct
27 Correct 824 ms 45996 KB Output is correct
28 Correct 1191 ms 72012 KB Output is correct
29 Correct 1205 ms 67696 KB Output is correct
30 Correct 1149 ms 67668 KB Output is correct
31 Correct 1316 ms 73552 KB Output is correct
32 Correct 21 ms 45148 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 45912 KB Output is correct
2 Correct 174 ms 45904 KB Output is correct
3 Correct 162 ms 45916 KB Output is correct
4 Correct 167 ms 45984 KB Output is correct
5 Correct 178 ms 45912 KB Output is correct
6 Correct 30 ms 62036 KB Output is correct
7 Correct 33 ms 61920 KB Output is correct
8 Correct 45 ms 62032 KB Output is correct
9 Correct 94 ms 63316 KB Output is correct
10 Correct 30 ms 53856 KB Output is correct
11 Correct 24 ms 53748 KB Output is correct
12 Correct 72 ms 56652 KB Output is correct
13 Correct 32 ms 53844 KB Output is correct
14 Correct 29 ms 53748 KB Output is correct
15 Correct 772 ms 83536 KB Output is correct
16 Correct 5178 ms 84836 KB Output is correct
17 Correct 20 ms 45144 KB Output is correct
18 Correct 21 ms 45148 KB Output is correct
19 Correct 22 ms 45144 KB Output is correct
20 Correct 22 ms 45396 KB Output is correct
21 Correct 26 ms 45388 KB Output is correct
22 Correct 21 ms 45404 KB Output is correct
23 Correct 22 ms 45404 KB Output is correct
24 Correct 19 ms 45292 KB Output is correct
25 Correct 19 ms 45400 KB Output is correct
26 Correct 26 ms 45252 KB Output is correct
27 Correct 64 ms 47748 KB Output is correct
28 Correct 19 ms 45300 KB Output is correct
29 Correct 798 ms 45980 KB Output is correct
30 Correct 1146 ms 71920 KB Output is correct
31 Correct 4511 ms 82192 KB Output is correct
32 Correct 4865 ms 82280 KB Output is correct
33 Correct 1191 ms 67536 KB Output is correct
34 Correct 4733 ms 76632 KB Output is correct
35 Correct 1324 ms 67676 KB Output is correct
36 Correct 5027 ms 76524 KB Output is correct
37 Correct 1274 ms 74044 KB Output is correct
38 Correct 4842 ms 82800 KB Output is correct
39 Correct 19 ms 46428 KB Output is correct
40 Correct 4809 ms 76628 KB Output is correct