oj.uz

Submission #897457

# Submission time Handle Problem Language Result Execution time Memory
897457 2024-01-03T06:40:33 Z Sir_Ahmed_Imran Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 210500 KB 
                              ///~~~LOTA~~~///
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
#define nl '\n'
#define ff first
#define ss second
#define ll long long 
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
#define N 10000000
int n,m;
int x[5000][100];
int y[5000][100];
int dp[5000][100][100];
void compute_dp(){
    for(int i=0;i<m;i++)
        for(int j=0;j<m;j++)
            dp[n-1][i][j]=abs(x[n-1][i]-x[n-1][j]);
    for(int i=n-2;i>=0;i--){
        for(int j=0;j<m;j++){
            for(int k=0;k<m;k++){
                dp[i][j][k]=1e9;
                for(int l=0;l<m;l++)
                    dp[i][j][k]=min(dp[i][j][k],
                    dp[i+1][l][k]+abs(x[i][j]-x[i][l])+y[i][l]);
            }
        }
    }
}
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++)
            x[i][j+1]=x[i][j]+H[i][j];
    for(int i=0;i<n-1;i++)
        for(int j=0;j<m;j++)
            y[i][j]=V[i][j];
    compute_dp();
}
void changeV(int p,int q,int w){
    y[p][q]=w;
    if(max(n,m)<20) compute_dp();
}
void changeH(int p,int q,int w){
    for(int i=m-1;i>0;i--)
        x[p][i]-=x[p][i-1];
    x[p][q+1]=w;
    for(int i=0;i<m-1;i++)
        x[p][i+1]+=x[p][i];
    if(max(n,m)<20) compute_dp();
}
int escape(int p,int q){
    if(max(n,m)>20) compute_dp();
    return dp[0][p][q];
}

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 34 ms 205660 KB Output is correct
2 Correct 35 ms 205640 KB Output is correct
3 Correct 4957 ms 207596 KB Output is correct
4 Correct 34 ms 205796 KB Output is correct
5 Correct 33 ms 205780 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

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 4440 KB Output is correct
3 Correct 1 ms 4440 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 1 ms 8672 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 8536 KB Output is correct
8 Correct 2 ms 8540 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 59 ms 9628 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 12997 ms 10804 KB Output is correct
2 Correct 12695 ms 10808 KB Output is correct
3 Correct 13253 ms 10804 KB Output is correct
4 Correct 13224 ms 10800 KB Output is correct
5 Correct 12844 ms 10800 KB Output is correct
6 Correct 1 ms 4440 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 13656 ms 10804 KB Output is correct
10 Correct 1 ms 6492 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 141 ms 87644 KB Output is correct
2 Correct 133 ms 93292 KB Output is correct
3 Correct 118 ms 93284 KB Output is correct
4 Correct 12974 ms 92308 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 13094 ms 11056 KB Output is correct
2 Correct 12815 ms 10804 KB Output is correct
3 Correct 13493 ms 10808 KB Output is correct
4 Correct 13188 ms 10804 KB Output is correct
5 Correct 12796 ms 10808 KB Output is correct
6 Correct 112 ms 87828 KB Output is correct
7 Correct 123 ms 89536 KB Output is correct
8 Correct 127 ms 87644 KB Output is correct
9 Correct 11477 ms 88696 KB Output is correct
10 Correct 33 ms 205648 KB Output is correct
11 Correct 39 ms 205652 KB Output is correct
12 Correct 5623 ms 208236 KB Output is correct
13 Correct 34 ms 205656 KB Output is correct
14 Correct 34 ms 205904 KB Output is correct
15 Correct 1 ms 4440 KB Output is correct
16 Correct 1 ms 4540 KB Output is correct
17 Correct 1 ms 4444 KB Output is correct
18 Correct 2 ms 8536 KB Output is correct
19 Correct 2 ms 8540 KB Output is correct
20 Correct 2 ms 8540 KB Output is correct
21 Correct 2 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 59 ms 10664 KB Output is correct
26 Correct 2 ms 8540 KB Output is correct
27 Correct 13067 ms 10876 KB Output is correct
28 Execution timed out 20037 ms 210500 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 12936 ms 10880 KB Output is correct
2 Correct 12736 ms 10868 KB Output is correct
3 Correct 13345 ms 10880 KB Output is correct
4 Correct 13231 ms 10884 KB Output is correct
5 Correct 12813 ms 10884 KB Output is correct
6 Correct 127 ms 207708 KB Output is correct
7 Correct 107 ms 207696 KB Output is correct
8 Correct 113 ms 207924 KB Output is correct
9 Correct 8796 ms 209152 KB Output is correct
10 Correct 33 ms 205660 KB Output is correct
11 Correct 33 ms 205716 KB Output is correct
12 Correct 5257 ms 207976 KB Output is correct
13 Correct 33 ms 205656 KB Output is correct
14 Correct 33 ms 205792 KB Output is correct
15 Runtime error 136 ms 25696 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -