oj.uz

Submission #1021308

# Submission time Handle Problem Language Result Execution time Memory
1021308 2024-07-12T16:49:06 Z amirhoseinfar1385 Wombats (IOI13_wombats) C++17
100 / 100
 3073 ms 157944 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=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];
            }
        }
    }
    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 50 ms 100436 KB Output is correct
2 Correct 48 ms 100272 KB Output is correct
3 Correct 77 ms 103252 KB Output is correct
4 Correct 46 ms 100308 KB Output is correct
5 Correct 43 ms 100444 KB Output is correct
6 Correct 37 ms 90196 KB Output is correct
7 Correct 38 ms 90196 KB Output is correct
8 Correct 38 ms 90200 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 90212 KB Output is correct
2 Correct 38 ms 90216 KB Output is correct
3 Correct 37 ms 90260 KB Output is correct
4 Correct 37 ms 90220 KB Output is correct
5 Correct 38 ms 90192 KB Output is correct
6 Correct 39 ms 90332 KB Output is correct
7 Correct 38 ms 90196 KB Output is correct
8 Correct 40 ms 90196 KB Output is correct
9 Correct 37 ms 90204 KB Output is correct
10 Correct 38 ms 90384 KB Output is correct
11 Correct 74 ms 92656 KB Output is correct
12 Correct 38 ms 90272 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 91220 KB Output is correct
2 Correct 96 ms 91220 KB Output is correct
3 Correct 96 ms 91216 KB Output is correct
4 Correct 100 ms 91216 KB Output is correct
5 Correct 99 ms 91228 KB Output is correct
6 Correct 38 ms 90192 KB Output is correct
7 Correct 38 ms 90196 KB Output is correct
8 Correct 38 ms 90196 KB Output is correct
9 Correct 344 ms 91292 KB Output is correct
10 Correct 38 ms 90204 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 108560 KB Output is correct
2 Correct 46 ms 108364 KB Output is correct
3 Correct 46 ms 108368 KB Output is correct
4 Correct 65 ms 109576 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 91244 KB Output is correct
2 Correct 95 ms 91216 KB Output is correct
3 Correct 97 ms 91216 KB Output is correct
4 Correct 95 ms 91212 KB Output is correct
5 Correct 99 ms 91216 KB Output is correct
6 Correct 47 ms 108368 KB Output is correct
7 Correct 52 ms 108432 KB Output is correct
8 Correct 46 ms 108376 KB Output is correct
9 Correct 66 ms 109604 KB Output is correct
10 Correct 43 ms 100432 KB Output is correct
11 Correct 45 ms 100444 KB Output is correct
12 Correct 80 ms 102856 KB Output is correct
13 Correct 43 ms 100440 KB Output is correct
14 Correct 43 ms 100384 KB Output is correct
15 Correct 43 ms 90196 KB Output is correct
16 Correct 38 ms 90220 KB Output is correct
17 Correct 38 ms 90192 KB Output is correct
18 Correct 43 ms 90208 KB Output is correct
19 Correct 38 ms 90204 KB Output is correct
20 Correct 38 ms 90176 KB Output is correct
21 Correct 38 ms 90252 KB Output is correct
22 Correct 37 ms 90320 KB Output is correct
23 Correct 36 ms 90240 KB Output is correct
24 Correct 36 ms 90196 KB Output is correct
25 Correct 74 ms 92496 KB Output is correct
26 Correct 38 ms 90192 KB Output is correct
27 Correct 322 ms 91268 KB Output is correct
28 Correct 777 ms 131788 KB Output is correct
29 Correct 759 ms 124632 KB Output is correct
30 Correct 770 ms 124760 KB Output is correct
31 Correct 794 ms 133124 KB Output is correct
32 Correct 40 ms 90196 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 91216 KB Output is correct
2 Correct 95 ms 91244 KB Output is correct
3 Correct 97 ms 91220 KB Output is correct
4 Correct 96 ms 91216 KB Output is correct
5 Correct 98 ms 91252 KB Output is correct
6 Correct 46 ms 108336 KB Output is correct
7 Correct 46 ms 108356 KB Output is correct
8 Correct 46 ms 108376 KB Output is correct
9 Correct 65 ms 109576 KB Output is correct
10 Correct 46 ms 100284 KB Output is correct
11 Correct 54 ms 100432 KB Output is correct
12 Correct 84 ms 102856 KB Output is correct
13 Correct 43 ms 100436 KB Output is correct
14 Correct 42 ms 100440 KB Output is correct
15 Correct 858 ms 155460 KB Output is correct
16 Correct 2997 ms 157288 KB Output is correct
17 Correct 39 ms 90520 KB Output is correct
18 Correct 38 ms 90048 KB Output is correct
19 Correct 39 ms 90204 KB Output is correct
20 Correct 37 ms 90356 KB Output is correct
21 Correct 38 ms 90192 KB Output is correct
22 Correct 38 ms 90196 KB Output is correct
23 Correct 38 ms 90196 KB Output is correct
24 Correct 38 ms 90348 KB Output is correct
25 Correct 38 ms 90192 KB Output is correct
26 Correct 38 ms 90196 KB Output is correct
27 Correct 75 ms 92508 KB Output is correct
28 Correct 38 ms 90200 KB Output is correct
29 Correct 314 ms 91340 KB Output is correct
30 Correct 763 ms 132584 KB Output is correct
31 Correct 2837 ms 157196 KB Output is correct
32 Correct 2882 ms 157392 KB Output is correct
33 Correct 760 ms 125524 KB Output is correct
34 Correct 2837 ms 146284 KB Output is correct
35 Correct 845 ms 125524 KB Output is correct
36 Correct 2958 ms 146340 KB Output is correct
37 Correct 906 ms 134088 KB Output is correct
38 Correct 3042 ms 157944 KB Output is correct
39 Correct 42 ms 90196 KB Output is correct
40 Correct 3073 ms 146124 KB Output is correct