oj.uz

답안 #1021323

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1021323 2024-07-12T16:58:16 Z amirhoseinfar1385 웜뱃 (IOI13_wombats) C++17
100 / 100
 2442 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=15,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

# 결과 실행 시간 메모리 Grader output
1 Correct 75 ms 189780 KB Output is correct
2 Correct 76 ms 189776 KB Output is correct
3 Correct 117 ms 192744 KB Output is correct
4 Correct 64 ms 189780 KB Output is correct
5 Correct 65 ms 189784 KB Output is correct
6 Correct 62 ms 178964 KB Output is correct
7 Correct 73 ms 178884 KB Output is correct
8 Correct 71 ms 178960 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 84 ms 178772 KB Output is correct
2 Correct 61 ms 178804 KB Output is correct
3 Correct 71 ms 179024 KB Output is correct
4 Correct 73 ms 179024 KB Output is correct
5 Correct 67 ms 179024 KB Output is correct
6 Correct 62 ms 178924 KB Output is correct
7 Correct 63 ms 178936 KB Output is correct
8 Correct 60 ms 179028 KB Output is correct
9 Correct 66 ms 179024 KB Output is correct
10 Correct 68 ms 179024 KB Output is correct
11 Correct 112 ms 181328 KB Output is correct
12 Correct 70 ms 179028 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 180208 KB Output is correct
2 Correct 114 ms 180304 KB Output is correct
3 Correct 111 ms 180300 KB Output is correct
4 Correct 132 ms 180216 KB Output is correct
5 Correct 118 ms 180132 KB Output is correct
6 Correct 70 ms 178828 KB Output is correct
7 Correct 69 ms 179024 KB Output is correct
8 Correct 70 ms 178968 KB Output is correct
9 Correct 260 ms 180308 KB Output is correct
10 Correct 69 ms 178920 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 74 ms 197972 KB Output is correct
2 Correct 78 ms 197972 KB Output is correct
3 Correct 69 ms 197968 KB Output is correct
4 Correct 99 ms 199260 KB Output is correct

Subtask #5
21.0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 105 ms 180200 KB Output is correct
2 Correct 128 ms 180308 KB Output is correct
3 Correct 107 ms 180144 KB Output is correct
4 Correct 105 ms 180308 KB Output is correct
5 Correct 108 ms 180308 KB Output is correct
6 Correct 70 ms 197888 KB Output is correct
7 Correct 82 ms 198032 KB Output is correct
8 Correct 83 ms 197832 KB Output is correct
9 Correct 102 ms 199340 KB Output is correct
10 Correct 75 ms 189776 KB Output is correct
11 Correct 70 ms 189776 KB Output is correct
12 Correct 108 ms 192592 KB Output is correct
13 Correct 71 ms 189844 KB Output is correct
14 Correct 73 ms 189780 KB Output is correct
15 Correct 70 ms 178772 KB Output is correct
16 Correct 68 ms 178776 KB Output is correct
17 Correct 76 ms 178776 KB Output is correct
18 Correct 79 ms 179160 KB Output is correct
19 Correct 74 ms 179028 KB Output is correct
20 Correct 69 ms 178980 KB Output is correct
21 Correct 71 ms 179136 KB Output is correct
22 Correct 71 ms 179036 KB Output is correct
23 Correct 71 ms 179064 KB Output is correct
24 Correct 84 ms 179028 KB Output is correct
25 Correct 115 ms 181480 KB Output is correct
26 Correct 77 ms 179028 KB Output is correct
27 Correct 272 ms 180304 KB Output is correct
28 Correct 624 ms 229412 KB Output is correct
29 Correct 646 ms 220760 KB Output is correct
30 Correct 642 ms 221012 KB Output is correct
31 Correct 702 ms 231128 KB Output is correct
32 Correct 70 ms 179024 KB Output is correct

Subtask #6
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 109 ms 180304 KB Output is correct
2 Correct 134 ms 180304 KB Output is correct
3 Correct 113 ms 180304 KB Output is correct
4 Correct 110 ms 180304 KB Output is correct
5 Correct 117 ms 180140 KB Output is correct
6 Correct 78 ms 197880 KB Output is correct
7 Correct 78 ms 197888 KB Output is correct
8 Correct 79 ms 197968 KB Output is correct
9 Correct 112 ms 199272 KB Output is correct
10 Correct 80 ms 189872 KB Output is correct
11 Correct 75 ms 189780 KB Output is correct
12 Correct 123 ms 192592 KB Output is correct
13 Correct 79 ms 189776 KB Output is correct
14 Correct 72 ms 189780 KB Output is correct
15 Correct 900 ms 262144 KB Output is correct
16 Correct 2367 ms 262144 KB Output is correct
17 Correct 72 ms 178884 KB Output is correct
18 Correct 73 ms 178804 KB Output is correct
19 Correct 68 ms 178772 KB Output is correct
20 Correct 70 ms 179028 KB Output is correct
21 Correct 69 ms 179028 KB Output is correct
22 Correct 67 ms 179028 KB Output is correct
23 Correct 75 ms 179028 KB Output is correct
24 Correct 69 ms 179132 KB Output is correct
25 Correct 66 ms 179024 KB Output is correct
26 Correct 70 ms 179024 KB Output is correct
27 Correct 104 ms 181412 KB Output is correct
28 Correct 76 ms 178916 KB Output is correct
29 Correct 256 ms 180240 KB Output is correct
30 Correct 624 ms 228688 KB Output is correct
31 Correct 2143 ms 260296 KB Output is correct
32 Correct 2161 ms 260300 KB Output is correct
33 Correct 674 ms 220496 KB Output is correct
34 Correct 2257 ms 246504 KB Output is correct
35 Correct 652 ms 220504 KB Output is correct
36 Correct 2260 ms 246416 KB Output is correct
37 Correct 771 ms 230744 KB Output is correct
38 Correct 2252 ms 261304 KB Output is correct
39 Correct 69 ms 179024 KB Output is correct
40 Correct 2442 ms 246688 KB Output is correct