oj.uz

Submission #1012545

# Submission time Handle Problem Language Result Execution time Memory
1012545 2024-07-02T10:18:32 Z amirhoseinfar1385 Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 35240 KB 
#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
const long long maxn=5000+10,maxm=200+10;
long long allr[maxn][maxm],allc[maxn][maxm],dp[maxn][maxm],n,m,ps[maxm],suf[maxm],inf=1e11+5,psmx[maxn],sufmx[maxn];

void calc(){
    for(long long k=1;k<=m;k++){
        for(long long j=1;j<=m;j++){
            ps[j]=ps[j-1]+allr[n][j-1];
        }
        for(long long j=m;j>=1;j--){
            suf[j]=suf[j+1]+allr[n][j];
        }
        for(int j=1;j<=m;j++){
            if(j<=k){
                dp[j][k]=ps[k]-ps[j];
            }else{
                dp[j][k]=suf[k]-suf[j];
            }
        }
    //    for(long long j=1;j<=m;j++){
      //      cout<<dp[j][k]<<" ";
     //   }
       // cout<<endl;
        psmx[0]=sufmx[m+1]=inf;
        for(long long i=n-1;i>=1;i--){
            for(long long j=1;j<=m;j++){
                ps[j]=ps[j-1]+allr[i][j-1];
            }
            for(long long j=m;j>=1;j--){
                suf[j]=suf[j+1]+allr[i][j];
            }
            for(long long j=1;j<=m;j++){
                psmx[j]=min(psmx[j-1],suf[j]+dp[j][k]+allc[i][j]);
            }
            for(long long j=m;j>=1;j--){
                sufmx[j]=min(sufmx[j+1],ps[j]+dp[j][k]+allc[i][j]);
            }
            for(long long j=1;j<=m;j++){
            //    cout<<psmx[j-1]<<" "<<suf[j]<<" "<<sufmx[j+1]<<" "<<ps[j]<<endl;
                dp[j][k]=min(dp[j][k]+allc[i][j],min(psmx[j-1]-suf[j],sufmx[j+1]-ps[j]));
            }
        //    cout<<"salam"<<endl;
          //  for(long long j=1;j<=m;j++){
            //    cout<<dp[j][k]<<" ";
        //    }
          //  cout<<endl;
        }
    }
}

void init(int R,int C,int H[5000][200],int V[5000][200]) {
    n=R;
    m=C;
    for(long long i=1;i<=n;i++){
        for(long long j=1;j<=m-1;j++){
            allr[i][j]=H[i-1][j-1];
        }
    }
    for(long long i=1;i<=n-1;i++){
        for(long long j=1;j<=m;j++){
            allc[i][j]=V[i-1][j-1];          
        }
    }
    calc();
}

void changeH(int P,int Q,int W) {
    P++;
    Q++;
    allr[P][Q]=W;
    calc();
}

void changeV(int P,int Q,int W) {
    P++;
    Q++;
    allc[P][Q]=W;
    calc();
}

int escape(int V1,int V2) {
    V1++;
    V2++;
    return dp[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 18 ms 17072 KB Output is correct
2 Correct 18 ms 17076 KB Output is correct
3 Correct 54 ms 19680 KB Output is correct
4 Correct 17 ms 16988 KB Output is correct
5 Correct 17 ms 16988 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4696 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8660 KB Output is correct
7 Correct 2 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 2 ms 8540 KB Output is correct
11 Correct 49 ms 10836 KB Output is correct
12 Correct 2 ms 8540 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 471 ms 8776 KB Output is correct
2 Correct 458 ms 8796 KB Output is correct
3 Correct 489 ms 8804 KB Output is correct
4 Correct 508 ms 8796 KB Output is correct
5 Correct 445 ms 8796 KB Output is correct
6 Correct 1 ms 4444 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 2206 ms 8792 KB Output is correct
10 Correct 1 ms 8636 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 26716 KB Output is correct
2 Correct 71 ms 26712 KB Output is correct
3 Correct 73 ms 26968 KB Output is correct
4 Correct 103 ms 28248 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 420 ms 8792 KB Output is correct
2 Correct 436 ms 8540 KB Output is correct
3 Correct 432 ms 8796 KB Output is correct
4 Correct 441 ms 8796 KB Output is correct
5 Correct 430 ms 8796 KB Output is correct
6 Correct 72 ms 26712 KB Output is correct
7 Correct 73 ms 26796 KB Output is correct
8 Correct 74 ms 26712 KB Output is correct
9 Correct 93 ms 28240 KB Output is correct
10 Correct 17 ms 17040 KB Output is correct
11 Correct 17 ms 17080 KB Output is correct
12 Correct 56 ms 19716 KB Output is correct
13 Correct 17 ms 16984 KB Output is correct
14 Correct 22 ms 16988 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct
16 Correct 1 ms 4444 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 1 ms 8640 KB Output is correct
19 Correct 1 ms 8540 KB Output is correct
20 Correct 1 ms 8540 KB Output is correct
21 Correct 1 ms 8540 KB Output is correct
22 Correct 1 ms 8540 KB Output is correct
23 Correct 1 ms 8540 KB Output is correct
24 Correct 1 ms 8540 KB Output is correct
25 Correct 41 ms 10832 KB Output is correct
26 Correct 1 ms 8536 KB Output is correct
27 Correct 1947 ms 8796 KB Output is correct
28 Execution timed out 20059 ms 30516 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 396 ms 8796 KB Output is correct
2 Correct 372 ms 8536 KB Output is correct
3 Correct 383 ms 8788 KB Output is correct
4 Correct 398 ms 8796 KB Output is correct
5 Correct 393 ms 8792 KB Output is correct
6 Correct 73 ms 25332 KB Output is correct
7 Correct 65 ms 25176 KB Output is correct
8 Correct 63 ms 26716 KB Output is correct
9 Correct 82 ms 26708 KB Output is correct
10 Correct 15 ms 16988 KB Output is correct
11 Correct 15 ms 16476 KB Output is correct
12 Correct 51 ms 19796 KB Output is correct
13 Correct 17 ms 16988 KB Output is correct
14 Correct 14 ms 16988 KB Output is correct
15 Correct 4281 ms 35240 KB Output is correct
16 Execution timed out 20006 ms 33052 KB Time limit exceeded
17 Halted 0 ms 0 KB -