oj.uz

Submission #1021327

# Submission time Handle Problem Language Result Execution time Memory
1021327 2024-07-12T17:00:29 Z amirhoseinfar1385 Wombats (IOI13_wombats) C++17
100 / 100
 2557 ms 159560 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];
    pair<int,int>allv[maxm*maxm];
    int ted=0;
    void build(){
        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;
                }
            }
        }
        for(int i=m;i>=1;i--){
          for(int j=1;j<=m;j++){
            allv[ted]=make_pair(i,j);
            ted++;
          }
        }
    }
    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){
        for(int l=0;l<ted;l++){
            r=allv[l].first;
            c=allv[l].second;
           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;
        }
    }
 
    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;
    seg.build();
    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 40 ms 100692 KB Output is correct
2 Correct 40 ms 100828 KB Output is correct
3 Correct 81 ms 103504 KB Output is correct
4 Correct 42 ms 100688 KB Output is correct
5 Correct 41 ms 100688 KB Output is correct
6 Correct 37 ms 90460 KB Output is correct
7 Correct 39 ms 90448 KB Output is correct
8 Correct 36 ms 90448 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 90564 KB Output is correct
2 Correct 42 ms 90452 KB Output is correct
3 Correct 36 ms 90448 KB Output is correct
4 Correct 36 ms 90716 KB Output is correct
5 Correct 37 ms 90708 KB Output is correct
6 Correct 36 ms 90704 KB Output is correct
7 Correct 37 ms 90668 KB Output is correct
8 Correct 36 ms 90716 KB Output is correct
9 Correct 36 ms 90600 KB Output is correct
10 Correct 43 ms 90708 KB Output is correct
11 Correct 79 ms 92880 KB Output is correct
12 Correct 37 ms 90508 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 91460 KB Output is correct
2 Correct 81 ms 91476 KB Output is correct
3 Correct 84 ms 91548 KB Output is correct
4 Correct 105 ms 91472 KB Output is correct
5 Correct 82 ms 91356 KB Output is correct
6 Correct 35 ms 90452 KB Output is correct
7 Correct 36 ms 90448 KB Output is correct
8 Correct 38 ms 90448 KB Output is correct
9 Correct 260 ms 91552 KB Output is correct
10 Correct 36 ms 90452 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 108884 KB Output is correct
2 Correct 46 ms 108864 KB Output is correct
3 Correct 45 ms 108880 KB Output is correct
4 Correct 73 ms 110164 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 83 ms 91472 KB Output is correct
2 Correct 81 ms 91532 KB Output is correct
3 Correct 85 ms 91532 KB Output is correct
4 Correct 83 ms 91476 KB Output is correct
5 Correct 84 ms 91472 KB Output is correct
6 Correct 46 ms 108884 KB Output is correct
7 Correct 44 ms 108884 KB Output is correct
8 Correct 43 ms 108884 KB Output is correct
9 Correct 74 ms 110160 KB Output is correct
10 Correct 43 ms 100688 KB Output is correct
11 Correct 43 ms 100692 KB Output is correct
12 Correct 81 ms 103516 KB Output is correct
13 Correct 53 ms 100692 KB Output is correct
14 Correct 42 ms 100688 KB Output is correct
15 Correct 35 ms 90448 KB Output is correct
16 Correct 36 ms 90460 KB Output is correct
17 Correct 37 ms 90412 KB Output is correct
18 Correct 37 ms 90608 KB Output is correct
19 Correct 35 ms 90492 KB Output is correct
20 Correct 36 ms 90544 KB Output is correct
21 Correct 36 ms 90548 KB Output is correct
22 Correct 43 ms 90708 KB Output is correct
23 Correct 36 ms 90580 KB Output is correct
24 Correct 37 ms 90712 KB Output is correct
25 Correct 76 ms 93012 KB Output is correct
26 Correct 37 ms 90716 KB Output is correct
27 Correct 253 ms 91544 KB Output is correct
28 Correct 621 ms 132896 KB Output is correct
29 Correct 594 ms 125712 KB Output is correct
30 Correct 599 ms 125524 KB Output is correct
31 Correct 629 ms 134480 KB Output is correct
32 Correct 37 ms 90448 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 91548 KB Output is correct
2 Correct 81 ms 91472 KB Output is correct
3 Correct 83 ms 91484 KB Output is correct
4 Correct 87 ms 91484 KB Output is correct
5 Correct 88 ms 91404 KB Output is correct
6 Correct 44 ms 108880 KB Output is correct
7 Correct 46 ms 108880 KB Output is correct
8 Correct 46 ms 108880 KB Output is correct
9 Correct 65 ms 110156 KB Output is correct
10 Correct 47 ms 100688 KB Output is correct
11 Correct 41 ms 100692 KB Output is correct
12 Correct 82 ms 103628 KB Output is correct
13 Correct 43 ms 100692 KB Output is correct
14 Correct 47 ms 100944 KB Output is correct
15 Correct 746 ms 158032 KB Output is correct
16 Correct 2224 ms 159560 KB Output is correct
17 Correct 35 ms 90496 KB Output is correct
18 Correct 37 ms 90584 KB Output is correct
19 Correct 36 ms 90620 KB Output is correct
20 Correct 36 ms 90704 KB Output is correct
21 Correct 36 ms 90716 KB Output is correct
22 Correct 36 ms 90568 KB Output is correct
23 Correct 33 ms 90716 KB Output is correct
24 Correct 37 ms 90712 KB Output is correct
25 Correct 36 ms 90652 KB Output is correct
26 Correct 36 ms 90704 KB Output is correct
27 Correct 79 ms 93008 KB Output is correct
28 Correct 41 ms 90704 KB Output is correct
29 Correct 254 ms 91484 KB Output is correct
30 Correct 602 ms 133004 KB Output is correct
31 Correct 2115 ms 157252 KB Output is correct
32 Correct 2114 ms 157232 KB Output is correct
33 Correct 624 ms 125784 KB Output is correct
34 Correct 2065 ms 146000 KB Output is correct
35 Correct 581 ms 125780 KB Output is correct
36 Correct 2178 ms 146068 KB Output is correct
37 Correct 639 ms 134348 KB Output is correct
38 Correct 2368 ms 157948 KB Output is correct
39 Correct 33 ms 90436 KB Output is correct
40 Correct 2557 ms 146124 KB Output is correct