oj.uz

Submission #815863

# Submission time Handle Problem Language Result Execution time Memory
815863 2023-08-09T01:41:06 Z Magikarp4000 Wombats (IOI13_wombats) C++17
39 / 100
 20000 ms 262144 KB 
#include "wombats.h"
#include <bits/stdc++.h>
using namespace std;
#define OPTM ios_base::sync_with_stdio(0); cin.tie(0);
#define INF int(1e9+7)
#define ln '\n' 
#define ll long long
#define ull unsigned long long
#define ui unsigned int
#define us unsigned short
#define FOR(i,s,n) for (int i = s; i < n; i++)
#define FORR(i,n,s) for (int i = n; i > s; i--)
#define FORX(u, arr) for (auto u : arr)
#define PB push_back
#define F first
#define S second
#define PII pair<int, int>
#define PLL pair<ll, ll>
#define UM unordered_map
#define US unordered_set
#define PQ priority_queue
#define ALL(v) v.begin(), v.end()
const ll LLINF = 1e18+1;

const int MAXN = 5e3+5, MAXM = 1e2+5;
int r,c,h[MAXN][MAXM],v[MAXN][MAXM];
int p[MAXN][MAXM], d[MAXN][MAXM][MAXM], dp[MAXN][MAXM][MAXM];

void calcdist(int row) {
    FOR(i,0,c) FOR(j,0,c) d[row][i][j] = INF;
    FOR(i,0,c) {
        FOR(j,0,c) {
            FOR(k,0,c) {
                d[row][i][j] = min(d[row][i][j], abs(p[row][k]-p[row][i])+abs(p[row+1][k]-p[row+1][j])+v[row][k]);
            }
        }
    }
}

void calcdp() {
    FORR(row,r-2,-1) {
        FOR(i,0,c) FOR(j,0,c) dp[row][i][j] = INF;
        FOR(i,0,c) {
            FOR(j,0,c) {
                FOR(k,0,c) {
                    dp[row][i][j] = min(dp[row][i][j], d[row][i][k]+dp[row+1][k][j]);
                }
            }
        }
    }
}

void init(int R, int C, int H[5000][200], int V[5000][200]) {
    r = R, c = C;
    FOR(i,0,r) FOR(j,0,c) h[i][j] = H[i][j], v[i][j] = V[i][j];
    FOR(i,0,r) FOR(j,1,c) p[i][j] = p[i][j-1]+h[i][j-1];
    FOR(row,0,r) FOR(i,0,c) FOR(j,0,c) d[row][i][j] = dp[row][i][j] = INF;
    FOR(i,0,c) FOR(j,0,c) dp[r-1][i][j] = abs(p[r-1][i]-p[r-1][j]);
    FOR(row,0,r-1) calcdist(row);
    calcdp();
}

void changeH(int P, int Q, int W) {
    h[P][Q] = W;
    FOR(j,1,c) p[P][j] = p[P][j-1]+h[P][j-1];
    if (P == r-1) {
        FOR(i,0,c) FOR(j,0,c) dp[r-1][i][j] = abs(p[r-1][i]-p[r-1][j]);
    }
    if (P > 0) calcdist(P-1);
    if (P < r-1) calcdist(P);
    calcdp();
}

void changeV(int P, int Q, int W) {
    v[P][Q] = W;
    calcdist(P);
    calcdp();
}

int escape(int V1, int V2) {
    // FOR(i,0,r) {
    //     FOR(j,1,c) cout << p[i][j] << " ";
    //     cout << ln;
    // }
    // FOR(i,0,c) {
    //     FOR(j,0,c) cout << d[1][i][j] << " ";
    //     cout << ln;
    // }
    return dp[0][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 65 ms 49184 KB Output is correct
2 Correct 77 ms 49192 KB Output is correct
3 Correct 119 ms 51976 KB Output is correct
4 Correct 66 ms 49200 KB Output is correct
5 Correct 72 ms 49204 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 312 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 312 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 1 ms 852 KB Output is correct
6 Correct 2 ms 896 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 1 ms 852 KB Output is correct
9 Correct 1 ms 852 KB Output is correct
10 Correct 1 ms 852 KB Output is correct
11 Correct 54 ms 3176 KB Output is correct
12 Correct 1 ms 852 KB Output is correct

Subtask #3
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10189 ms 9232 KB Output is correct
2 Correct 9775 ms 9224 KB Output is correct
3 Correct 10235 ms 9420 KB Output is correct
4 Correct 10243 ms 9324 KB Output is correct
5 Correct 9753 ms 9320 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Execution timed out 20088 ms 9316 KB Time limit exceeded
10 Halted 0 ms 0 KB -

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 100 ms 59228 KB Output is correct
2 Correct 143 ms 59320 KB Output is correct
3 Correct 122 ms 59340 KB Output is correct
4 Correct 131 ms 60676 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 10301 ms 9236 KB Output is correct
2 Correct 9768 ms 9220 KB Output is correct
3 Correct 10630 ms 9324 KB Output is correct
4 Correct 10469 ms 9324 KB Output is correct
5 Correct 10095 ms 9328 KB Output is correct
6 Correct 122 ms 59332 KB Output is correct
7 Correct 107 ms 59220 KB Output is correct
8 Correct 122 ms 59344 KB Output is correct
9 Correct 147 ms 60624 KB Output is correct
10 Correct 67 ms 49184 KB Output is correct
11 Correct 66 ms 49092 KB Output is correct
12 Correct 119 ms 51916 KB Output is correct
13 Correct 70 ms 49204 KB Output is correct
14 Correct 69 ms 49200 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 1 ms 852 KB Output is correct
19 Correct 1 ms 852 KB Output is correct
20 Correct 1 ms 852 KB Output is correct
21 Correct 1 ms 852 KB Output is correct
22 Correct 1 ms 852 KB Output is correct
23 Correct 2 ms 852 KB Output is correct
24 Correct 1 ms 852 KB Output is correct
25 Correct 53 ms 3200 KB Output is correct
26 Correct 1 ms 852 KB Output is correct
27 Execution timed out 20072 ms 9316 KB Time limit exceeded
28 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 10398 ms 9228 KB Output is correct
2 Correct 9974 ms 9220 KB Output is correct
3 Correct 10579 ms 9324 KB Output is correct
4 Correct 10419 ms 9324 KB Output is correct
5 Correct 10162 ms 9336 KB Output is correct
6 Correct 122 ms 59328 KB Output is correct
7 Correct 103 ms 59324 KB Output is correct
8 Correct 110 ms 59352 KB Output is correct
9 Correct 143 ms 60620 KB Output is correct
10 Correct 68 ms 49180 KB Output is correct
11 Correct 72 ms 49192 KB Output is correct
12 Correct 128 ms 51916 KB Output is correct
13 Correct 67 ms 49196 KB Output is correct
14 Correct 74 ms 49192 KB Output is correct
15 Runtime error 302 ms 262144 KB Execution killed with signal 9
16 Halted 0 ms 0 KB -