oj.uz

Submission #1021325

# Submission time Handle Problem Language Result Execution time Memory
1021325 2024-07-12T16:59:16 Z amirhoseinfar1385 Wombats (IOI13_wombats) C++17
100 / 100
 2398 ms 150548 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=25,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];
    vector<pair<int,int>>allv;
    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.push_back(make_pair(i,j));
          }
        }
    }
    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){
        int l=0;
        while(l<(int)allv.size()){
            r=allv[l].first;
            c=allv[l].second;
            l++;
           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 42 ms 99664 KB Output is correct
2 Correct 41 ms 99616 KB Output is correct
3 Correct 80 ms 101216 KB Output is correct
4 Correct 46 ms 99664 KB Output is correct
5 Correct 41 ms 99668 KB Output is correct
6 Correct 36 ms 89988 KB Output is correct
7 Correct 42 ms 89964 KB Output is correct
8 Correct 36 ms 89944 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 90008 KB Output is correct
2 Correct 36 ms 90040 KB Output is correct
3 Correct 38 ms 89940 KB Output is correct
4 Correct 35 ms 90080 KB Output is correct
5 Correct 46 ms 89936 KB Output is correct
6 Correct 39 ms 90164 KB Output is correct
7 Correct 35 ms 89936 KB Output is correct
8 Correct 37 ms 89940 KB Output is correct
9 Correct 35 ms 90024 KB Output is correct
10 Correct 37 ms 89936 KB Output is correct
11 Correct 76 ms 91984 KB Output is correct
12 Correct 36 ms 89936 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 85 ms 90972 KB Output is correct
2 Correct 84 ms 90844 KB Output is correct
3 Correct 91 ms 90968 KB Output is correct
4 Correct 105 ms 91044 KB Output is correct
5 Correct 85 ms 91036 KB Output is correct
6 Correct 36 ms 89936 KB Output is correct
7 Correct 36 ms 89948 KB Output is correct
8 Correct 37 ms 89936 KB Output is correct
9 Correct 268 ms 90972 KB Output is correct
10 Correct 36 ms 89848 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 107784 KB Output is correct
2 Correct 57 ms 107856 KB Output is correct
3 Correct 50 ms 107856 KB Output is correct
4 Correct 74 ms 109140 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 91100 KB Output is correct
2 Correct 87 ms 90964 KB Output is correct
3 Correct 88 ms 91056 KB Output is correct
4 Correct 85 ms 90972 KB Output is correct
5 Correct 90 ms 91220 KB Output is correct
6 Correct 45 ms 107856 KB Output is correct
7 Correct 46 ms 107860 KB Output is correct
8 Correct 46 ms 107860 KB Output is correct
9 Correct 67 ms 109136 KB Output is correct
10 Correct 44 ms 99672 KB Output is correct
11 Correct 42 ms 99668 KB Output is correct
12 Correct 79 ms 102208 KB Output is correct
13 Correct 42 ms 99664 KB Output is correct
14 Correct 40 ms 99664 KB Output is correct
15 Correct 47 ms 89940 KB Output is correct
16 Correct 36 ms 89936 KB Output is correct
17 Correct 36 ms 89936 KB Output is correct
18 Correct 36 ms 89988 KB Output is correct
19 Correct 36 ms 90084 KB Output is correct
20 Correct 37 ms 90024 KB Output is correct
21 Correct 38 ms 89940 KB Output is correct
22 Correct 36 ms 89972 KB Output is correct
23 Correct 36 ms 90136 KB Output is correct
24 Correct 36 ms 89940 KB Output is correct
25 Correct 95 ms 92108 KB Output is correct
26 Correct 37 ms 89940 KB Output is correct
27 Correct 266 ms 90960 KB Output is correct
28 Correct 611 ms 127996 KB Output is correct
29 Correct 688 ms 121640 KB Output is correct
30 Correct 599 ms 121600 KB Output is correct
31 Correct 550 ms 129364 KB Output is correct
32 Correct 34 ms 89936 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 90964 KB Output is correct
2 Correct 71 ms 90964 KB Output is correct
3 Correct 76 ms 90960 KB Output is correct
4 Correct 87 ms 90964 KB Output is correct
5 Correct 87 ms 91008 KB Output is correct
6 Correct 44 ms 107856 KB Output is correct
7 Correct 45 ms 107860 KB Output is correct
8 Correct 50 ms 107864 KB Output is correct
9 Correct 65 ms 109136 KB Output is correct
10 Correct 45 ms 99668 KB Output is correct
11 Correct 40 ms 99664 KB Output is correct
12 Correct 79 ms 102596 KB Output is correct
13 Correct 42 ms 99668 KB Output is correct
14 Correct 43 ms 99912 KB Output is correct
15 Correct 679 ms 149196 KB Output is correct
16 Correct 2339 ms 150548 KB Output is correct
17 Correct 34 ms 89852 KB Output is correct
18 Correct 34 ms 89852 KB Output is correct
19 Correct 36 ms 89936 KB Output is correct
20 Correct 35 ms 89948 KB Output is correct
21 Correct 35 ms 89944 KB Output is correct
22 Correct 37 ms 89936 KB Output is correct
23 Correct 35 ms 89908 KB Output is correct
24 Correct 35 ms 89948 KB Output is correct
25 Correct 35 ms 89944 KB Output is correct
26 Correct 37 ms 89944 KB Output is correct
27 Correct 81 ms 92500 KB Output is correct
28 Correct 36 ms 89940 KB Output is correct
29 Correct 264 ms 90964 KB Output is correct
30 Correct 624 ms 127828 KB Output is correct
31 Correct 2168 ms 148496 KB Output is correct
32 Correct 2295 ms 148492 KB Output is correct
33 Correct 657 ms 121428 KB Output is correct
34 Correct 2276 ms 138904 KB Output is correct
35 Correct 612 ms 121388 KB Output is correct
36 Correct 2287 ms 138904 KB Output is correct
37 Correct 741 ms 129464 KB Output is correct
38 Correct 2346 ms 148952 KB Output is correct
39 Correct 40 ms 90032 KB Output is correct
40 Correct 2398 ms 138824 KB Output is correct