oj.uz

Submission #570377

# Submission time Handle Problem Language Result Execution time Memory
570377 2022-05-29T11:37:11 Z cheissmart Wombats (IOI13_wombats) C++14
76 / 100
 20000 ms 248960 KB 
#include "wombats.h"
#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define EB emplace_back
#define MP make_pair
#define SZ(v) int((v).size())
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

string _reset = "\u001b[0m", _yellow = "\u001b[33m", _bold = "\u001b[1m";
void DBG() { cerr << "]" << _reset << endl; }
template<class H, class...T> void DBG(H h, T ...t) {
    cerr << to_string(h);
    if(sizeof ...(t)) cerr << ", ";
    DBG(t...);
}
#ifdef CHEISSMART
#define debug(...) cerr << _yellow << _bold << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define debug(...)
#endif

const int INF = 1e9 + 7, mxR = 5000, mxC = 200, K = 15;

int h[5000][200], v[5000][200], dp[5000][200];
int R, C;

struct node {
    int a[mxC][mxC];
    node() { memset(a, 0x3f, sizeof a); }
    void build(int tl, int tr) {
        for(int s = 0; s < C; s++) {
            for(int j = 0; j < C; j++)
                dp[tl][j] = INF;
            auto gogo = [&] (int row) {
                for(int i = 0; i + 1 < C; i++)
                    dp[row][i + 1] = min(dp[row][i + 1], dp[row][i] + h[row][i]);
                for(int i = C - 2; i >= 0; i--)
                    dp[row][i] = min(dp[row][i], dp[row][i + 1] + h[row][i]);
            };
            dp[tl][s] = 0;
            gogo(tl);
            for(int i = tl + 1; i <= tr; i++) {
                for(int j = 0; j < C; j++)
                    dp[i][j] = dp[i - 1][j] + v[i - 1][j];
                gogo(i);
            }
            for(int t = 0; t < C; t++)
                a[s][t] = dp[tr][t];
        }
    }
    void add(node& l, node& r) {
        for(int s = 0; s < C; s++) {
            for(int t = 0; t < C; t++) {
                int mn = INF;
                for(int k = 0; k < C; k++)
                    mn = min(mn, l.a[s][k] + r.a[k][t]);
                a[s][t] = mn;
            }
        }
    }
} t[350 * 4];

void upd(int pos, int v = 1, int tl = 0, int tr = R - 1) {
    if(tr - tl <= K) {
        t[v].build(tl, tr);
        return;
    }
    int tm = (tl + tr) / 2;
    if(pos < tm)
        upd(pos, v * 2, tl, tm);
    else 
        upd(pos, v * 2 + 1, tm, tr);
    t[v].add(t[v * 2], t[v * 2 + 1]);
}

void build(int v = 1, int tl = 0, int tr = R - 1) {
    if(tr - tl <= K) {
        t[v].build(tl, tr);
        return;
    }
    int tm = (tl + tr) / 2;
    build(v * 2, tl, tm);
    build(v * 2 + 1, tm, tr);
    t[v].add(t[v * 2], t[v * 2 + 1]);
}

void init(int _R, int _C, int _h[5000][200], int _v[5000][200]) {
    memcpy(h, _h, sizeof h);
    memcpy(v, _v, sizeof v);
    R = _R, C = _C;
    build();
}  

void changeH(int P, int Q, int W) {
    h[P][Q] = W;
    if(P) upd(P - 1);
    upd(P);
}

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

int escape(int V1, int V2) {
    return t[1].a[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 94 ms 235044 KB Output is correct
2 Correct 91 ms 235128 KB Output is correct
3 Correct 151 ms 237868 KB Output is correct
4 Correct 93 ms 235340 KB Output is correct
5 Correct 102 ms 235052 KB Output is correct
6 Correct 86 ms 227404 KB Output is correct
7 Correct 83 ms 227300 KB Output is correct
8 Correct 87 ms 227300 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 96 ms 227276 KB Output is correct
2 Correct 102 ms 227268 KB Output is correct
3 Correct 87 ms 227252 KB Output is correct
4 Correct 93 ms 227368 KB Output is correct
5 Correct 91 ms 227280 KB Output is correct
6 Correct 97 ms 227284 KB Output is correct
7 Correct 85 ms 227360 KB Output is correct
8 Correct 97 ms 227360 KB Output is correct
9 Correct 84 ms 227376 KB Output is correct
10 Correct 89 ms 227376 KB Output is correct
11 Correct 162 ms 229708 KB Output is correct
12 Correct 93 ms 227356 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 704 ms 227632 KB Output is correct
2 Correct 480 ms 227624 KB Output is correct
3 Correct 895 ms 227640 KB Output is correct
4 Correct 504 ms 227692 KB Output is correct
5 Correct 699 ms 227628 KB Output is correct
6 Correct 88 ms 227244 KB Output is correct
7 Correct 90 ms 227252 KB Output is correct
8 Correct 96 ms 227312 KB Output is correct
9 Correct 3503 ms 227636 KB Output is correct
10 Correct 88 ms 227276 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 239056 KB Output is correct
2 Correct 96 ms 238968 KB Output is correct
3 Correct 99 ms 239084 KB Output is correct
4 Correct 131 ms 240388 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 714 ms 227684 KB Output is correct
2 Correct 477 ms 227628 KB Output is correct
3 Correct 898 ms 227760 KB Output is correct
4 Correct 522 ms 227684 KB Output is correct
5 Correct 691 ms 227640 KB Output is correct
6 Correct 94 ms 239032 KB Output is correct
7 Correct 100 ms 239028 KB Output is correct
8 Correct 113 ms 239108 KB Output is correct
9 Correct 138 ms 240488 KB Output is correct
10 Correct 90 ms 235088 KB Output is correct
11 Correct 110 ms 235084 KB Output is correct
12 Correct 179 ms 238004 KB Output is correct
13 Correct 91 ms 235048 KB Output is correct
14 Correct 111 ms 235048 KB Output is correct
15 Correct 112 ms 227224 KB Output is correct
16 Correct 89 ms 227276 KB Output is correct
17 Correct 86 ms 227240 KB Output is correct
18 Correct 90 ms 227372 KB Output is correct
19 Correct 96 ms 227328 KB Output is correct
20 Correct 100 ms 227288 KB Output is correct
21 Correct 98 ms 227376 KB Output is correct
22 Correct 97 ms 227284 KB Output is correct
23 Correct 95 ms 227404 KB Output is correct
24 Correct 91 ms 227276 KB Output is correct
25 Correct 151 ms 229628 KB Output is correct
26 Correct 90 ms 227304 KB Output is correct
27 Correct 3531 ms 227632 KB Output is correct
28 Correct 9925 ms 243560 KB Output is correct
29 Correct 8427 ms 240860 KB Output is correct
30 Correct 8414 ms 240704 KB Output is correct
31 Correct 8492 ms 244884 KB Output is correct
32 Correct 97 ms 227296 KB Output is correct

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 703 ms 227636 KB Output is correct
2 Correct 471 ms 227632 KB Output is correct
3 Correct 900 ms 227672 KB Output is correct
4 Correct 487 ms 227640 KB Output is correct
5 Correct 665 ms 227672 KB Output is correct
6 Correct 103 ms 238984 KB Output is correct
7 Correct 93 ms 239068 KB Output is correct
8 Correct 90 ms 239048 KB Output is correct
9 Correct 148 ms 240372 KB Output is correct
10 Correct 104 ms 235024 KB Output is correct
11 Correct 89 ms 235164 KB Output is correct
12 Correct 154 ms 237892 KB Output is correct
13 Correct 92 ms 235108 KB Output is correct
14 Correct 102 ms 235056 KB Output is correct
15 Correct 6275 ms 248960 KB Output is correct
16 Execution timed out 20074 ms 247576 KB Time limit exceeded
17 Halted 0 ms 0 KB -