oj.uz

Submission #1021285

# Submission time Handle Problem Language Result Execution time Memory
1021285 2024-07-12T16:40:26 Z amirhoseinfar1385 Wombats (IOI13_wombats) C++17
76 / 100
 906 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=10,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 ;
        }
    //    cout<<cl<<" "<<cr<<" "<<r<<" "<<c<<endl;
        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;
      |      ^~~
wombats.cpp: In constructor 'segment::segment()':
wombats.cpp:55:29: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   55 |         for(int i=0;i<(1<<lg+1);i++){
      |                           ~~^~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 192144 KB Output is correct
2 Correct 81 ms 192104 KB Output is correct
3 Correct 113 ms 194340 KB Output is correct
4 Correct 75 ms 192084 KB Output is correct
5 Correct 103 ms 192164 KB Output is correct
6 Correct 97 ms 179540 KB Output is correct
7 Correct 69 ms 179580 KB Output is correct
8 Correct 79 ms 179744 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 91 ms 179540 KB Output is correct
2 Correct 73 ms 179692 KB Output is correct
3 Correct 72 ms 179516 KB Output is correct
4 Correct 87 ms 179736 KB Output is correct
5 Correct 73 ms 179640 KB Output is correct
6 Correct 70 ms 179796 KB Output is correct
7 Correct 70 ms 179796 KB Output is correct
8 Correct 70 ms 179708 KB Output is correct
9 Correct 70 ms 179792 KB Output is correct
10 Correct 70 ms 179792 KB Output is correct
11 Correct 149 ms 181836 KB Output is correct
12 Correct 70 ms 179796 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 181064 KB Output is correct
2 Correct 116 ms 181072 KB Output is correct
3 Correct 124 ms 181028 KB Output is correct
4 Correct 140 ms 181028 KB Output is correct
5 Correct 120 ms 181076 KB Output is correct
6 Correct 73 ms 179688 KB Output is correct
7 Correct 70 ms 179540 KB Output is correct
8 Correct 90 ms 179536 KB Output is correct
9 Correct 307 ms 181076 KB Output is correct
10 Correct 70 ms 179576 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 200020 KB Output is correct
2 Correct 91 ms 200020 KB Output is correct
3 Correct 82 ms 200020 KB Output is correct
4 Correct 100 ms 201300 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 181072 KB Output is correct
2 Correct 121 ms 180896 KB Output is correct
3 Correct 130 ms 181072 KB Output is correct
4 Correct 120 ms 181072 KB Output is correct
5 Correct 145 ms 180948 KB Output is correct
6 Correct 83 ms 200016 KB Output is correct
7 Correct 97 ms 200056 KB Output is correct
8 Correct 84 ms 200020 KB Output is correct
9 Correct 101 ms 201300 KB Output is correct
10 Correct 81 ms 192080 KB Output is correct
11 Correct 84 ms 192084 KB Output is correct
12 Correct 116 ms 194384 KB Output is correct
13 Correct 79 ms 192192 KB Output is correct
14 Correct 98 ms 192084 KB Output is correct
15 Correct 72 ms 179540 KB Output is correct
16 Correct 80 ms 179648 KB Output is correct
17 Correct 71 ms 179540 KB Output is correct
18 Correct 91 ms 179776 KB Output is correct
19 Correct 71 ms 179668 KB Output is correct
20 Correct 71 ms 179800 KB Output is correct
21 Correct 71 ms 179796 KB Output is correct
22 Correct 95 ms 179688 KB Output is correct
23 Correct 71 ms 179768 KB Output is correct
24 Correct 71 ms 179792 KB Output is correct
25 Correct 129 ms 181704 KB Output is correct
26 Correct 71 ms 179792 KB Output is correct
27 Correct 279 ms 180932 KB Output is correct
28 Correct 812 ms 241336 KB Output is correct
29 Correct 747 ms 230228 KB Output is correct
30 Correct 756 ms 230228 KB Output is correct
31 Correct 800 ms 242260 KB Output is correct
32 Correct 73 ms 179696 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 111 ms 180832 KB Output is correct
2 Correct 119 ms 180816 KB Output is correct
3 Correct 127 ms 180820 KB Output is correct
4 Correct 123 ms 180816 KB Output is correct
5 Correct 139 ms 181036 KB Output is correct
6 Correct 78 ms 199988 KB Output is correct
7 Correct 104 ms 199980 KB Output is correct
8 Correct 80 ms 200016 KB Output is correct
9 Correct 99 ms 200940 KB Output is correct
10 Correct 79 ms 192016 KB Output is correct
11 Correct 74 ms 192084 KB Output is correct
12 Correct 121 ms 193616 KB Output is correct
13 Correct 83 ms 192088 KB Output is correct
14 Correct 85 ms 192076 KB Output is correct
15 Runtime error 906 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -