oj.uz

Submission #815865

# Submission time Handle Problem Language Result Execution time Memory
815865 2023-08-09T01:43:37 Z Magikarp4000 Wombats (IOI13_wombats) C++17
34 / 100
 20000 ms 60160 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;
    // }
    calcdp();
    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
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 49108 KB Output is correct
2 Correct 71 ms 49156 KB Output is correct
3 Execution timed out 20044 ms 50724 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 60 ms 872 KB Output is correct
5 Correct 75 ms 868 KB Output is correct
6 Correct 68 ms 864 KB Output is correct
7 Correct 54 ms 864 KB Output is correct
8 Correct 39 ms 828 KB Output is correct
9 Correct 62 ms 852 KB Output is correct
10 Correct 43 ms 852 KB Output is correct
11 Execution timed out 20043 ms 1492 KB Time limit exceeded
12 Halted 0 ms 0 KB -

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 10425 ms 9152 KB Output is correct
2 Correct 10248 ms 9172 KB Output is correct
3 Correct 10877 ms 9244 KB Output is correct
4 Correct 10750 ms 9240 KB Output is correct
5 Correct 10314 ms 9240 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 Correct 11495 ms 9244 KB Output is correct
10 Correct 0 ms 340 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 59264 KB Output is correct
2 Correct 236 ms 59272 KB Output is correct
3 Correct 225 ms 59264 KB Output is correct
4 Correct 19884 ms 59956 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 10278 ms 9156 KB Output is correct
2 Correct 9833 ms 9156 KB Output is correct
3 Correct 10516 ms 9240 KB Output is correct
4 Correct 10279 ms 9248 KB Output is correct
5 Correct 10081 ms 9240 KB Output is correct
6 Correct 222 ms 59236 KB Output is correct
7 Correct 214 ms 59264 KB Output is correct
8 Correct 234 ms 59260 KB Output is correct
9 Correct 19125 ms 60060 KB Output is correct
10 Correct 73 ms 49168 KB Output is correct
11 Correct 75 ms 49160 KB Output is correct
12 Execution timed out 20048 ms 50592 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 10104 ms 9156 KB Output is correct
2 Correct 9706 ms 9152 KB Output is correct
3 Correct 10238 ms 9252 KB Output is correct
4 Correct 10158 ms 9244 KB Output is correct
5 Correct 9890 ms 9244 KB Output is correct
6 Correct 218 ms 59264 KB Output is correct
7 Correct 217 ms 59224 KB Output is correct
8 Correct 223 ms 59276 KB Output is correct
9 Correct 17643 ms 60160 KB Output is correct
10 Correct 73 ms 49164 KB Output is correct
11 Correct 73 ms 49128 KB Output is correct
12 Execution timed out 20021 ms 50552 KB Time limit exceeded
13 Halted 0 ms 0 KB -