oj.uz

Submission #1100983

# Submission time Handle Problem Language Result Execution time Memory
1100983 2024-10-15T07:23:53 Z alexander707070 Wombats (IOI13_wombats) C++14
55 / 100
 20000 ms 24484 KB 
#include<bits/stdc++.h>
#include "wombats.h"
using namespace std;

const int inf=1e9;

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

int dp[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(){
    for(int fin=1;fin<=m;fin++){
        
        for(int c=1;c<=m;c++){
            dp[fin][n%2][c]=getsum(n,min(c,fin),max(c,fin)-1);
        }

        for(int r=n-1;r>=1;r--){
            
            optl[1]=dp[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[fin][1-r%2][c]+cols[c][r]);
            }

            optr[m]=dp[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[fin][1-r%2][c]+cols[c][r]);
            }

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

    }
}

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];
        }
    }

    calcdp();
}

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();
}

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

    calcdp();
}

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

    return dp[V2][1][V1];
}

/*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

# Verdict Execution time Memory Grader output
1 Correct 11 ms 6748 KB Output is correct
2 Correct 11 ms 6736 KB Output is correct
3 Correct 51 ms 8264 KB Output is correct
4 Correct 10 ms 6736 KB Output is correct
5 Correct 11 ms 6908 KB Output is correct
6 Correct 1 ms 2384 KB Output is correct
7 Correct 1 ms 2556 KB Output is correct
8 Correct 1 ms 2384 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2384 KB Output is correct
2 Correct 1 ms 2384 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 6480 KB Output is correct
5 Correct 1 ms 6480 KB Output is correct
6 Correct 2 ms 6480 KB Output is correct
7 Correct 2 ms 6596 KB Output is correct
8 Correct 2 ms 6648 KB Output is correct
9 Correct 1 ms 6480 KB Output is correct
10 Correct 1 ms 6480 KB Output is correct
11 Correct 40 ms 7496 KB Output is correct
12 Correct 1 ms 6480 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 342 ms 6756 KB Output is correct
2 Correct 307 ms 6756 KB Output is correct
3 Correct 334 ms 6736 KB Output is correct
4 Correct 327 ms 6736 KB Output is correct
5 Correct 311 ms 6908 KB Output is correct
6 Correct 1 ms 2384 KB Output is correct
7 Correct 1 ms 2384 KB Output is correct
8 Correct 1 ms 2384 KB Output is correct
9 Correct 1616 ms 6736 KB Output is correct
10 Correct 1 ms 4436 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 12900 KB Output is correct
2 Correct 47 ms 12880 KB Output is correct
3 Correct 46 ms 12880 KB Output is correct
4 Correct 70 ms 13436 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 327 ms 6748 KB Output is correct
2 Correct 319 ms 6736 KB Output is correct
3 Correct 325 ms 6736 KB Output is correct
4 Correct 374 ms 6736 KB Output is correct
5 Correct 312 ms 6736 KB Output is correct
6 Correct 48 ms 13052 KB Output is correct
7 Correct 51 ms 12880 KB Output is correct
8 Correct 59 ms 13048 KB Output is correct
9 Correct 69 ms 13448 KB Output is correct
10 Correct 13 ms 6736 KB Output is correct
11 Correct 15 ms 6736 KB Output is correct
12 Correct 59 ms 8264 KB Output is correct
13 Correct 11 ms 6736 KB Output is correct
14 Correct 11 ms 6736 KB Output is correct
15 Correct 1 ms 2384 KB Output is correct
16 Correct 1 ms 2384 KB Output is correct
17 Correct 1 ms 2384 KB Output is correct
18 Correct 2 ms 6480 KB Output is correct
19 Correct 2 ms 6480 KB Output is correct
20 Correct 1 ms 6480 KB Output is correct
21 Correct 1 ms 6480 KB Output is correct
22 Correct 1 ms 6480 KB Output is correct
23 Correct 1 ms 6480 KB Output is correct
24 Correct 1 ms 6480 KB Output is correct
25 Correct 39 ms 7384 KB Output is correct
26 Correct 1 ms 6648 KB Output is correct
27 Correct 1619 ms 6736 KB Output is correct
28 Execution timed out 20060 ms 18700 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 331 ms 6756 KB Output is correct
2 Correct 318 ms 6736 KB Output is correct
3 Correct 329 ms 6736 KB Output is correct
4 Correct 331 ms 6736 KB Output is correct
5 Correct 314 ms 6736 KB Output is correct
6 Correct 55 ms 12892 KB Output is correct
7 Correct 49 ms 12880 KB Output is correct
8 Correct 49 ms 12880 KB Output is correct
9 Correct 68 ms 13624 KB Output is correct
10 Correct 11 ms 6736 KB Output is correct
11 Correct 42 ms 6736 KB Output is correct
12 Correct 47 ms 8264 KB Output is correct
13 Correct 11 ms 6784 KB Output is correct
14 Correct 10 ms 6552 KB Output is correct
15 Correct 3344 ms 16596 KB Output is correct
16 Execution timed out 20036 ms 24484 KB Time limit exceeded
17 Halted 0 ms 0 KB -