oj.uz

답안 #1100992

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1100992 2024-10-15T08:06:19 Z alexander707070 웜뱃 (IOI13_wombats) C++14
55 / 100
 20000 ms 19632 KB 
#include<bits/stdc++.h>
#include "wombats.h"
using namespace std;

const int bucket_sz=5007;

const int inf=1e9;

int n,m;
int rows[5007][207];
int cols[207][5007];

int bucket[5007];
pair<int,int> seg[5007];

int dp[27][207][2][207];
int optl[207],optr[207];

int getsum(int row,int l,int r){
    return rows[row][r]-rows[row][l-1];
}

void calcdp(int buck,int from,int to){

    for(int fin=1;fin<=m;fin++){
        for(int c=1;c<=m;c++){
            dp[buck][fin][to%2][c]=getsum(to,min(c,fin),max(c,fin)-1);
        }

        for(int r=to-1;r>=from;r--){
            
            optl[1]=dp[buck][fin][1-r%2][1]+cols[1][r];
            for(int c=2;c<=m;c++){
                optl[c]=min(optl[c-1]+getsum(r,c-1,c-1),dp[buck][fin][1-r%2][c]+cols[c][r]);
            }

            optr[m]=dp[buck][fin][1-r%2][m]+cols[m][r];
            for(int c=m-1;c>=1;c--){
                optr[c]=min(optr[c+1]+getsum(r,c,c),dp[buck][fin][1-r%2][c]+cols[c][r]);
            }

            for(int c=1;c<=m;c++){
                dp[buck][fin][r%2][c]=min(optl[c],optr[c]);
            }
        }
    }
}

int dp2[207][2][207];

int dist(int buck,int from,int to){
    return dp[buck][to][seg[buck].first%2][from];
}

void solve(){
    for(int start=1;start<=m;start++){
        for(int i=0;i<=n/bucket_sz;i++){
            for(int c=1;c<=m;c++){

                dp2[start][i%2][c]=inf;

                if(i==0){
                    dp2[start][i%2][c]=dist(i,start,c);
                    continue;
                }

                for(int k=1;k<=m;k++){
                    dp2[start][i%2][c]=min(dp2[start][i%2][c],dist(i,k,c)+cols[k][seg[i-1].second]+dp2[start][1-i%2][k]);
                }
            }
        }
    }
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
//void init(int R,int C,vector< vector<int> > H,vector< vector<int> > V){
    n=R; m=C;

    for(int i=1;i<=n;i++){
        for(int f=1;f<=m-1;f++){
            rows[i][f]=H[i-1][f-1];
            rows[i][f]+=rows[i][f-1];
        }
    }
    for(int i=1;i<=m;i++){
        for(int f=1;f<=n-1;f++){
            cols[i][f]=V[f-1][i-1];
        }
    }

    for(int i=1;i<=n;i++){
        bucket[i]=i/bucket_sz;
        if(seg[bucket[i]].first==0)seg[bucket[i]].first=i;
        seg[bucket[i]].second=i;
    }

    for(int i=0;i<=n/bucket_sz;i++){
        calcdp(i,seg[i].first,seg[i].second);
    }
    solve();
}

void changeH(int P, int Q, int W) {
    P++; Q++;

    int dif=W-(rows[P][Q]-rows[P][Q-1]);
    for(int i=Q;i<=m-1;i++){
        rows[P][i]+=dif;
    }

    calcdp(bucket[P],seg[bucket[P]].first,seg[bucket[P]].second);
    solve();
}

void changeV(int P, int Q, int W){
    P++; Q++;
    cols[Q][P]=W;

    if(bucket[Q]==bucket[Q+1]){
        calcdp(bucket[Q],seg[bucket[Q]].first,seg[bucket[Q]].second);
    }
    solve();
}

int escape(int V1, int V2) {
    V1++; V2++;

    return dp2[V1][(n/bucket_sz)%2][V2];
}

/*int main(){

    init(4,1,{{}},{{1},{1},{1},{1}});

    cout<<escape(0,0)<<"\n";
    changeV(0,0,2);
    cout<<escape(0,0)<<"\n";
    changeV(1,0,2);
    cout<<escape(0,0)<<"\n";
    changeV(2,0,2)
    cout<<escape(0,0)<<"\n";

    init(3,4,{{0,2,5},{7,1,1},{0,4,0}},{{0,0,0,2},{0,3,4,7}});

    cout<<escape(2,1)<<"\n";
    cout<<escape(3,3)<<"\n";

    changeV(0,0,5);
    changeH(1,1,6);

    cout<<escape(2,1)<<"\n";
 
	return 0;
}*/

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 12 ms 8784 KB Output is correct
2 Correct 12 ms 8828 KB Output is correct
3 Correct 47 ms 10312 KB Output is correct
4 Correct 12 ms 8784 KB Output is correct
5 Correct 13 ms 8796 KB Output is correct
6 Correct 1 ms 4432 KB Output is correct
7 Correct 1 ms 4432 KB Output is correct
8 Correct 1 ms 4432 KB Output is correct

Subtask #2
12.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 4432 KB Output is correct
2 Correct 1 ms 4432 KB Output is correct
3 Correct 1 ms 4432 KB Output is correct
4 Correct 2 ms 6480 KB Output is correct
5 Correct 1 ms 6480 KB Output is correct
6 Correct 1 ms 6480 KB Output is correct
7 Correct 1 ms 6480 KB Output is correct
8 Correct 2 ms 6480 KB Output is correct
9 Correct 2 ms 6480 KB Output is correct
10 Correct 1 ms 6480 KB Output is correct
11 Correct 40 ms 7508 KB Output is correct
12 Correct 2 ms 6480 KB Output is correct

Subtask #3
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 338 ms 8784 KB Output is correct
2 Correct 312 ms 8784 KB Output is correct
3 Correct 332 ms 8988 KB Output is correct
4 Correct 341 ms 8808 KB Output is correct
5 Correct 319 ms 8952 KB Output is correct
6 Correct 1 ms 4432 KB Output is correct
7 Correct 1 ms 4452 KB Output is correct
8 Correct 1 ms 4432 KB Output is correct
9 Correct 1650 ms 8804 KB Output is correct
10 Correct 1 ms 6480 KB Output is correct

Subtask #4
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 50 ms 14672 KB Output is correct
2 Correct 52 ms 14916 KB Output is correct
3 Correct 51 ms 15092 KB Output is correct
4 Correct 75 ms 15688 KB Output is correct

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 331 ms 8800 KB Output is correct
2 Correct 317 ms 8784 KB Output is correct
3 Correct 331 ms 8784 KB Output is correct
4 Correct 344 ms 8800 KB Output is correct
5 Correct 312 ms 8800 KB Output is correct
6 Correct 52 ms 14928 KB Output is correct
7 Correct 59 ms 14912 KB Output is correct
8 Correct 54 ms 14928 KB Output is correct
9 Correct 80 ms 15580 KB Output is correct
10 Correct 12 ms 8784 KB Output is correct
11 Correct 12 ms 8828 KB Output is correct
12 Correct 48 ms 10312 KB Output is correct
13 Correct 13 ms 8784 KB Output is correct
14 Correct 20 ms 8824 KB Output is correct
15 Correct 1 ms 4432 KB Output is correct
16 Correct 1 ms 4432 KB Output is correct
17 Correct 1 ms 4432 KB Output is correct
18 Correct 2 ms 6628 KB Output is correct
19 Correct 1 ms 6480 KB Output is correct
20 Correct 2 ms 6480 KB Output is correct
21 Correct 1 ms 6480 KB Output is correct
22 Correct 2 ms 6480 KB Output is correct
23 Correct 1 ms 6480 KB Output is correct
24 Correct 2 ms 6480 KB Output is correct
25 Correct 70 ms 7512 KB Output is correct
26 Correct 2 ms 6480 KB Output is correct
27 Correct 1935 ms 8820 KB Output is correct
28 Execution timed out 20037 ms 17052 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 329 ms 8784 KB Output is correct
2 Correct 328 ms 8784 KB Output is correct
3 Correct 352 ms 8804 KB Output is correct
4 Correct 343 ms 8800 KB Output is correct
5 Correct 329 ms 8784 KB Output is correct
6 Correct 48 ms 14920 KB Output is correct
7 Correct 58 ms 14920 KB Output is correct
8 Correct 48 ms 14928 KB Output is correct
9 Correct 67 ms 15688 KB Output is correct
10 Correct 12 ms 8784 KB Output is correct
11 Correct 12 ms 8828 KB Output is correct
12 Correct 47 ms 10252 KB Output is correct
13 Correct 12 ms 8784 KB Output is correct
14 Correct 12 ms 8784 KB Output is correct
15 Correct 3394 ms 19548 KB Output is correct
16 Execution timed out 20052 ms 19632 KB Time limit exceeded
17 Halted 0 ms 0 KB -