oj.uz

Submission #964213

# Submission time Handle Problem Language Result Execution time Memory
964213 2024-04-16T12:22:53 Z Amr Wombats (IOI13_wombats) C++17
55 / 100
 20000 ms 33684 KB 
#include "wombats.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sz size()
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
int rows[5000][200], cols[5000][200],pre[5001][201],ans[5001][201];
int r,c;
void init(int R, int C, int H[5000][200], int V[5000][200]) {
    r = R, c = C;
    for(int i = 0; i < r; i++)
    {
        for(int j = 0; j <  c-1; j++) rows[i][j] = H[i][j];
    }
    for(int i = 0; i < c; i++)
    {
        for(int j = 0; j < r-1; j++)
        {
            cols[j][i] = V[j][i];
        }
    }
}

void changeH(int P, int Q, int W) {
    rows[P][Q] = W;
}

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

int escape(int V1, int V2) {
    for(int i = 0; i < r; i++)
    {
        for(int j = 0; j <  c; j++) ans[i][j] = 0;
    }
    for(int i = 0; i < r; i++)
    {
        for(int j = 1; j < c; j++)
        {
            pre[i][j] = pre[i][j-1]+rows[i][j-1];

        }

    }
    for(int i = 0; i < c; i++)
    {
        if(i==V1) ans[0][V1] = 0;
        else if(i<V1) ans[0][i] = pre[0][V1]-pre[0][i];
        else ans[0][i] = pre[0][i]-pre[0][V1];
      //  cout << ans[0][i] << " ";
    }
    //cout << endl;
    for(int i = 1; i < r; i++)
    {
        for(int j = 0; j < c; j++)
        {
            ans[i][j] = 1e18;
            for(int k = 0; k < c; k++)
            {
                if(k==j) ans[i][j] = min(ans[i][j],ans[i-1][k]+cols[i-1][k]);
                else if(k<j) ans[i][j] = min(ans[i][j],ans[i-1][k]+cols[i-1][k]+pre[i][j]-pre[i][k]);
                else ans[i][j] = min(ans[i][j],ans[i-1][k]+cols[i-1][k]+pre[i][k]-pre[i][j]);
            }
        }
    }
   //for(int i = 0; i < r; i++) {for(int j = 0; j < c; j++) cout << ans[i][j] << " "; cout << endl;}
    int best = 1e9;
    for(int i = 0; i < c ;i++)
    {
        if(i==V2) best = min(best,ans[r-1][i]);
        else if(i<V2) best = min(best,ans[r-1][i] +  pre[r-1][V2]-pre[r-1][i]);
        else best  = min(best,ans[r-1][i]+pre[r-1][i]-pre[r-1][V2]);
    }
    return best;
}

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;
      |      ^~~
wombats.cpp: In function 'int escape(int, int)':
wombats.cpp:60:25: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   60 |             ans[i][j] = 1e18;
      |                         ^~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 16984 KB Output is correct
2 Correct 23 ms 17240 KB Output is correct
3 Correct 8204 ms 19684 KB Output is correct
4 Correct 22 ms 16984 KB Output is correct
5 Correct 23 ms 16840 KB Output is correct
6 Correct 1 ms 4548 KB Output is correct
7 Correct 2 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 4444 KB Output is correct
3 Correct 1 ms 4444 KB Output is correct
4 Correct 8 ms 8540 KB Output is correct
5 Correct 7 ms 8540 KB Output is correct
6 Correct 6 ms 8696 KB Output is correct
7 Correct 6 ms 8540 KB Output is correct
8 Correct 6 ms 8536 KB Output is correct
9 Correct 6 ms 8696 KB Output is correct
10 Correct 5 ms 8540 KB Output is correct
11 Correct 2494 ms 11164 KB Output is correct
12 Correct 6 ms 8536 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 158 ms 8792 KB Output is correct
2 Correct 157 ms 8856 KB Output is correct
3 Correct 162 ms 8876 KB Output is correct
4 Correct 163 ms 8872 KB Output is correct
5 Correct 143 ms 8796 KB Output is correct
6 Correct 1 ms 4536 KB Output is correct
7 Correct 1 ms 4444 KB Output is correct
8 Correct 1 ms 4444 KB Output is correct
9 Correct 157 ms 8868 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 105 ms 23900 KB Output is correct
2 Correct 108 ms 23896 KB Output is correct
3 Correct 110 ms 24016 KB Output is correct
4 Correct 9548 ms 25308 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 150 ms 9040 KB Output is correct
2 Correct 145 ms 8864 KB Output is correct
3 Correct 155 ms 8796 KB Output is correct
4 Correct 175 ms 8792 KB Output is correct
5 Correct 148 ms 8868 KB Output is correct
6 Correct 116 ms 24016 KB Output is correct
7 Correct 88 ms 23900 KB Output is correct
8 Correct 98 ms 24012 KB Output is correct
9 Correct 10112 ms 25276 KB Output is correct
10 Correct 23 ms 17056 KB Output is correct
11 Correct 23 ms 16984 KB Output is correct
12 Correct 8222 ms 19936 KB Output is correct
13 Correct 24 ms 17048 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 8 ms 8540 KB Output is correct
19 Correct 7 ms 8540 KB Output is correct
20 Correct 9 ms 8540 KB Output is correct
21 Correct 6 ms 8536 KB Output is correct
22 Correct 5 ms 8540 KB Output is correct
23 Correct 7 ms 8540 KB Output is correct
24 Correct 6 ms 8540 KB Output is correct
25 Correct 2557 ms 10952 KB Output is correct
26 Correct 6 ms 8644 KB Output is correct
27 Correct 148 ms 8868 KB Output is correct
28 Execution timed out 20081 ms 27504 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 8796 KB Output is correct
2 Correct 151 ms 8860 KB Output is correct
3 Correct 166 ms 8872 KB Output is correct
4 Correct 156 ms 8872 KB Output is correct
5 Correct 159 ms 8796 KB Output is correct
6 Correct 110 ms 24012 KB Output is correct
7 Correct 99 ms 24000 KB Output is correct
8 Correct 123 ms 24016 KB Output is correct
9 Correct 9420 ms 25196 KB Output is correct
10 Correct 29 ms 17036 KB Output is correct
11 Correct 29 ms 17056 KB Output is correct
12 Correct 7980 ms 19596 KB Output is correct
13 Correct 27 ms 16988 KB Output is correct
14 Correct 22 ms 16988 KB Output is correct
15 Correct 2259 ms 33684 KB Output is correct
16 Execution timed out 20036 ms 31732 KB Time limit exceeded
17 Halted 0 ms 0 KB -