oj.uz

Submission #1021305

# Submission time Handle Problem Language Result Execution time Memory
1021305 2024-07-12T16:47:59 Z amirhoseinfar1385 Wombats (IOI13_wombats) C++17
100 / 100
 3433 ms 262144 KB 
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2")
#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn=5000+10,maxm=200+10,t=15,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];
            }
        }
    }
    vector<pair<int,int>>allv;
    void dfs(int cl,int cr,int r=m,int c=1){
        allv.clear();
        allv.push_back(make_pair(r,c));
        int l=0;
        while(l<(int)allv.size()){
            r=allv[l].first;
            c=allv[l].second;
            l++;
           if(r==0||c==m+1){
               continue;
           }
           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;
           allv.push_back(make_pair(r-1,c));
           if(r==m){
               allv.push_back(make_pair(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;
      |      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 191572 KB Output is correct
2 Correct 85 ms 191312 KB Output is correct
3 Correct 117 ms 193748 KB Output is correct
4 Correct 78 ms 191568 KB Output is correct
5 Correct 80 ms 191316 KB Output is correct
6 Correct 74 ms 180668 KB Output is correct
7 Correct 73 ms 180568 KB Output is correct
8 Correct 73 ms 180560 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 180564 KB Output is correct
2 Correct 75 ms 180724 KB Output is correct
3 Correct 79 ms 180616 KB Output is correct
4 Correct 84 ms 180820 KB Output is correct
5 Correct 74 ms 180596 KB Output is correct
6 Correct 82 ms 180672 KB Output is correct
7 Correct 76 ms 180816 KB Output is correct
8 Correct 82 ms 180816 KB Output is correct
9 Correct 80 ms 180588 KB Output is correct
10 Correct 75 ms 180796 KB Output is correct
11 Correct 116 ms 182608 KB Output is correct
12 Correct 75 ms 180744 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 181128 KB Output is correct
2 Correct 126 ms 181172 KB Output is correct
3 Correct 136 ms 180304 KB Output is correct
4 Correct 143 ms 180308 KB Output is correct
5 Correct 129 ms 180196 KB Output is correct
6 Correct 74 ms 178772 KB Output is correct
7 Correct 78 ms 179028 KB Output is correct
8 Correct 74 ms 178840 KB Output is correct
9 Correct 347 ms 180296 KB Output is correct
10 Correct 74 ms 179028 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 197972 KB Output is correct
2 Correct 95 ms 197968 KB Output is correct
3 Correct 91 ms 197968 KB Output is correct
4 Correct 154 ms 199440 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 180096 KB Output is correct
2 Correct 170 ms 180284 KB Output is correct
3 Correct 163 ms 180312 KB Output is correct
4 Correct 145 ms 180352 KB Output is correct
5 Correct 147 ms 180184 KB Output is correct
6 Correct 99 ms 198004 KB Output is correct
7 Correct 96 ms 197860 KB Output is correct
8 Correct 91 ms 197812 KB Output is correct
9 Correct 118 ms 199248 KB Output is correct
10 Correct 92 ms 189780 KB Output is correct
11 Correct 99 ms 189968 KB Output is correct
12 Correct 134 ms 192596 KB Output is correct
13 Correct 111 ms 189776 KB Output is correct
14 Correct 85 ms 189780 KB Output is correct
15 Correct 78 ms 179000 KB Output is correct
16 Correct 79 ms 179024 KB Output is correct
17 Correct 82 ms 178816 KB Output is correct
18 Correct 86 ms 178956 KB Output is correct
19 Correct 81 ms 179072 KB Output is correct
20 Correct 79 ms 179024 KB Output is correct
21 Correct 87 ms 179144 KB Output is correct
22 Correct 81 ms 179024 KB Output is correct
23 Correct 80 ms 178960 KB Output is correct
24 Correct 77 ms 179024 KB Output is correct
25 Correct 124 ms 181072 KB Output is correct
26 Correct 92 ms 179012 KB Output is correct
27 Correct 344 ms 180308 KB Output is correct
28 Correct 834 ms 228824 KB Output is correct
29 Correct 897 ms 220496 KB Output is correct
30 Correct 879 ms 220500 KB Output is correct
31 Correct 931 ms 230736 KB Output is correct
32 Correct 92 ms 178996 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 133 ms 180284 KB Output is correct
2 Correct 135 ms 180308 KB Output is correct
3 Correct 138 ms 180148 KB Output is correct
4 Correct 146 ms 180484 KB Output is correct
5 Correct 166 ms 180304 KB Output is correct
6 Correct 90 ms 197972 KB Output is correct
7 Correct 93 ms 197976 KB Output is correct
8 Correct 91 ms 197852 KB Output is correct
9 Correct 113 ms 199248 KB Output is correct
10 Correct 90 ms 189776 KB Output is correct
11 Correct 102 ms 189860 KB Output is correct
12 Correct 133 ms 192736 KB Output is correct
13 Correct 87 ms 189968 KB Output is correct
14 Correct 84 ms 189776 KB Output is correct
15 Correct 1022 ms 261316 KB Output is correct
16 Correct 3433 ms 262144 KB Output is correct
17 Correct 84 ms 178956 KB Output is correct
18 Correct 80 ms 178896 KB Output is correct
19 Correct 84 ms 179028 KB Output is correct
20 Correct 94 ms 179156 KB Output is correct
21 Correct 88 ms 179024 KB Output is correct
22 Correct 82 ms 179028 KB Output is correct
23 Correct 80 ms 179024 KB Output is correct
24 Correct 102 ms 179024 KB Output is correct
25 Correct 84 ms 178912 KB Output is correct
26 Correct 81 ms 179028 KB Output is correct
27 Correct 122 ms 181480 KB Output is correct
28 Correct 82 ms 179024 KB Output is correct
29 Correct 342 ms 180472 KB Output is correct
30 Correct 841 ms 228924 KB Output is correct
31 Correct 2924 ms 260300 KB Output is correct
32 Correct 3159 ms 260404 KB Output is correct
33 Correct 891 ms 220392 KB Output is correct
34 Correct 3301 ms 246468 KB Output is correct
35 Correct 877 ms 220756 KB Output is correct
36 Correct 3219 ms 246464 KB Output is correct
37 Correct 933 ms 230708 KB Output is correct
38 Correct 3202 ms 261156 KB Output is correct
39 Correct 75 ms 178876 KB Output is correct
40 Correct 3395 ms 246728 KB Output is correct