oj.uz

Submission #1021296

# Submission time Handle Problem Language Result Execution time Memory
1021296 2024-07-12T16:44:06 Z amirhoseinfar1385 Wombats (IOI13_wombats) C++17
100 / 100
 2850 ms 132668 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=35,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 ;
        }
        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;
      |      ^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 114004 KB Output is correct
2 Correct 50 ms 114036 KB Output is correct
3 Correct 94 ms 117428 KB Output is correct
4 Correct 46 ms 115748 KB Output is correct
5 Correct 45 ms 114000 KB Output is correct
6 Correct 39 ms 107612 KB Output is correct
7 Correct 39 ms 107604 KB Output is correct
8 Correct 40 ms 109652 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 107856 KB Output is correct
2 Correct 39 ms 107600 KB Output is correct
3 Correct 41 ms 107740 KB Output is correct
4 Correct 40 ms 107600 KB Output is correct
5 Correct 39 ms 107604 KB Output is correct
6 Correct 50 ms 107728 KB Output is correct
7 Correct 47 ms 107812 KB Output is correct
8 Correct 41 ms 109652 KB Output is correct
9 Correct 39 ms 107604 KB Output is correct
10 Correct 39 ms 107700 KB Output is correct
11 Correct 77 ms 110636 KB Output is correct
12 Correct 39 ms 107600 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 108116 KB Output is correct
2 Correct 104 ms 109868 KB Output is correct
3 Correct 102 ms 108052 KB Output is correct
4 Correct 99 ms 107908 KB Output is correct
5 Correct 123 ms 107860 KB Output is correct
6 Correct 39 ms 107608 KB Output is correct
7 Correct 40 ms 107612 KB Output is correct
8 Correct 39 ms 107612 KB Output is correct
9 Correct 348 ms 107860 KB Output is correct
10 Correct 44 ms 107712 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 119892 KB Output is correct
2 Correct 57 ms 119888 KB Output is correct
3 Correct 46 ms 121424 KB Output is correct
4 Correct 66 ms 120656 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 107968 KB Output is correct
2 Correct 99 ms 95736 KB Output is correct
3 Correct 100 ms 95728 KB Output is correct
4 Correct 99 ms 97876 KB Output is correct
5 Correct 113 ms 95908 KB Output is correct
6 Correct 56 ms 111316 KB Output is correct
7 Correct 52 ms 111304 KB Output is correct
8 Correct 41 ms 111288 KB Output is correct
9 Correct 63 ms 117844 KB Output is correct
10 Correct 42 ms 112464 KB Output is correct
11 Correct 42 ms 98908 KB Output is correct
12 Correct 88 ms 114040 KB Output is correct
13 Correct 41 ms 105556 KB Output is correct
14 Correct 40 ms 99068 KB Output is correct
15 Correct 37 ms 95572 KB Output is correct
16 Correct 45 ms 105752 KB Output is correct
17 Correct 32 ms 89684 KB Output is correct
18 Correct 41 ms 103588 KB Output is correct
19 Correct 50 ms 89940 KB Output is correct
20 Correct 51 ms 105780 KB Output is correct
21 Correct 34 ms 89828 KB Output is correct
22 Correct 37 ms 97536 KB Output is correct
23 Correct 40 ms 105808 KB Output is correct
24 Correct 35 ms 89888 KB Output is correct
25 Correct 86 ms 104784 KB Output is correct
26 Correct 42 ms 103764 KB Output is correct
27 Correct 369 ms 104024 KB Output is correct
28 Correct 673 ms 124972 KB Output is correct
29 Correct 683 ms 119120 KB Output is correct
30 Correct 686 ms 119120 KB Output is correct
31 Correct 735 ms 125560 KB Output is correct
32 Correct 39 ms 103764 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 89 ms 104016 KB Output is correct
2 Correct 100 ms 106008 KB Output is correct
3 Correct 102 ms 104020 KB Output is correct
4 Correct 118 ms 104020 KB Output is correct
5 Correct 102 ms 105832 KB Output is correct
6 Correct 45 ms 117076 KB Output is correct
7 Correct 45 ms 118424 KB Output is correct
8 Correct 45 ms 118356 KB Output is correct
9 Correct 64 ms 119372 KB Output is correct
10 Correct 42 ms 110680 KB Output is correct
11 Correct 42 ms 110676 KB Output is correct
12 Correct 78 ms 114004 KB Output is correct
13 Correct 42 ms 112464 KB Output is correct
14 Correct 42 ms 110708 KB Output is correct
15 Correct 601 ms 130980 KB Output is correct
16 Correct 2850 ms 132668 KB Output is correct
17 Correct 39 ms 105552 KB Output is correct
18 Correct 46 ms 103764 KB Output is correct
19 Correct 38 ms 105596 KB Output is correct
20 Correct 39 ms 105812 KB Output is correct
21 Correct 39 ms 105812 KB Output is correct
22 Correct 39 ms 105820 KB Output is correct
23 Correct 39 ms 105812 KB Output is correct
24 Correct 39 ms 103752 KB Output is correct
25 Correct 39 ms 105808 KB Output is correct
26 Correct 39 ms 103764 KB Output is correct
27 Correct 77 ms 104784 KB Output is correct
28 Correct 39 ms 105808 KB Output is correct
29 Correct 350 ms 106048 KB Output is correct
30 Correct 662 ms 124988 KB Output is correct
31 Correct 2431 ms 131552 KB Output is correct
32 Correct 2589 ms 131668 KB Output is correct
33 Correct 669 ms 119000 KB Output is correct
34 Correct 2574 ms 124388 KB Output is correct
35 Correct 675 ms 119120 KB Output is correct
36 Correct 2513 ms 124544 KB Output is correct
37 Correct 728 ms 126288 KB Output is correct
38 Correct 2647 ms 132296 KB Output is correct
39 Correct 39 ms 103760 KB Output is correct
40 Correct 2689 ms 124464 KB Output is correct