oj.uz

Submission #753986

# Submission time Handle Problem Language Result Execution time Memory
753986 2023-06-06T12:37:27 Z marvinthang Wombats (IOI13_wombats) C++17
100 / 100
 3700 ms 135064 KB 
/*************************************
*    author: marvinthang             *
*    created: 06.06.2023 17:13:07    *
*************************************/

#include "wombats.h"
#include <bits/stdc++.h>

using namespace std;

#define                  fi  first
#define                  se  second
#define                left  ___left
#define               right  ___right
#define                TIME  (1.0 * clock() / CLOCKS_PER_SEC)
#define             MASK(i)  (1LL << (i))
#define           BIT(x, i)  ((x) >> (i) & 1)
#define  __builtin_popcount  __builtin_popcountll
#define              ALL(v)  (v).begin(), (v).end()
#define           REP(i, n)  for (int i = 0, _n = (n); i < _n; ++i)
#define          REPD(i, n)  for (int i = (n); i--; )
#define        FOR(i, a, b)  for (int i = (a), _b = (b); i < _b; ++i) 
#define       FORD(i, b, a)  for (int i = (b), _a = (a); --i >= _a; ) 
#define       FORE(i, a, b)  for (int i = (a), _b = (b); i <= _b; ++i) 
#define      FORDE(i, b, a)  for (int i = (b), _a = (a); i >= _a; --i) 
#define        scan_op(...)  istream & operator >> (istream &in, __VA_ARGS__ &u)
#define       print_op(...)  ostream & operator << (ostream &out, const __VA_ARGS__ &u)
#ifdef LOCAL
    #include "debug.h"
#else
    #define file(name) if (fopen(name".inp", "r")) { freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout); }
    #define DB(...) 23
    #define db(...) 23
    #define debug(...) 23
#endif

template <class U, class V> scan_op(pair <U, V>)  { return in >> u.first >> u.second; }
template <class T> scan_op(vector <T>)  { for (size_t i = 0; i < u.size(); ++i) in >> u[i]; return in; }
template <class U, class V> print_op(pair <U, V>)  { return out << '(' << u.first << ", " << u.second << ')'; }
template <size_t i, class T> ostream & print_tuple_utils(ostream &out, const T &tup) { if constexpr(i == tuple_size<T>::value) return out << ")";  else return print_tuple_utils<i + 1, T>(out << (i ? ", " : "(") << get<i>(tup), tup); }
template <class ...U> print_op(tuple<U...>) { return print_tuple_utils<0, tuple<U...>>(out, u); }
template <class Con, class = decltype(begin(declval<Con>()))> typename enable_if <!is_same<Con, string>::value, ostream&>::type operator << (ostream &out, const Con &con) { out << '{'; for (__typeof(con.begin()) it = con.begin(); it != con.end(); ++it) out << (it == con.begin() ? "" : ", ") << *it; return out << '}'; }
template <class A, class B> bool minimize(A &a, B b)  { if (a > b) { a = b; return true; } return false; }
template <class A, class B> bool maximize(A &a, B b)  { if (a < b) { a = b; return true; } return false; }

// end of template

const int MAX_R = 5005;
const int MAX_C = 203;
const int MG = 15;

int R, C, H[MAX_R][MAX_C], V[MAX_R][MAX_C];
int st[(MAX_R / MG + 5) << 2][MAX_C][MAX_C], opt[MAX_C][MAX_C];

void solve(int id, int bl) {
    int l = bl * MG;
    int r = min(R, l + MG) - 1;
    REP(s, C) {
        st[id][s][s] = 0;
        FOR(y, s + 1, C) st[id][s][y] = st[id][s][y - 1] + H[l][y - 1];
        REPD(y, s) st[id][s][y] = st[id][s][y + 1] + H[l][y];
        FOR(x, l, r) {
            REP(y, C) st[id][s][y] += V[x][y];
            REP(y, C - 1) minimize(st[id][s][y + 1], st[id][s][y] + H[x + 1][y]);
            REPD(y, C - 1) minimize(st[id][s][y], st[id][s][y + 1] + H[x + 1][y]);
        }
    }
}

void pushUp(int id, int r) {
    r = r * MG + MG - 1;
    REP(x, C) {
        memset(st[id][x], 0x3f, C * sizeof(int));
        REPD(y, C) FORE(k, x ? opt[x - 1][y] : 0, y + 1 < C ? opt[x][y + 1] : C - 1) if (minimize(st[id][x][y], st[id << 1][x][k] + V[r][k] + st[id << 1 | 1][k][y])) opt[x][y] = k;
    }
}

void build(int i, int l, int r) {
    if (r - l == 1) {
        solve(i, l);
        return;
    }
    int m = l + r >> 1;
    build(i << 1, l, m);
    build(i << 1 | 1, m, r);
    pushUp(i, m - 1);
}

void update(int i, int l, int r, int p) {
    if (r - l == 1) {
        solve(i, l);
        return;
    }
    int m = l + r >> 1;
    if (p < m) update(i << 1, l, m, p);
    else update(i << 1 | 1, m, r, p);
    pushUp(i, m - 1);
}

void init(int r, int c, int h[5000][200], int v[5000][200]) {
    R = r; C = c;
    REP(i, R) REP(j, C - 1) H[i][j] = h[i][j];
    REP(i, R - 1) REP(j, C) V[i][j] = v[i][j];
    build(1, 0, (R - 1) / MG + 1);
}

void changeH(int P, int Q, int W) {
    H[P][Q] = W;
    update(1, 0, (R - 1) / MG + 1, P / MG);
}

void changeV(int P, int Q, int W) {
    V[P][Q] = W;
    update(1, 0, (R - 1) / MG + 1, P / MG);
}

int escape(int V1, int V2) {
    return st[1][V1][V2];
}

#ifdef LOCAL
#include <stdio.h>
#include <stdlib.h>
#include "wombats.h"

#define fail(s, x...) do { \
        fprintf(stderr, s "\n", ## x); \
        exit(1); \
    } while(0)

static int h[5000][200];
static int v[5000][200];

int main() {
    int R, C, E, P, Q, W, V1, V2, event, i, j;
    int res;

    FILE *f = fopen("wombats.in", "r");
    freopen("wombats.out", "w", stdout);
    if (!f)
        fail("Failed to open input file.");


    res = fscanf(f, "%d%d", &R, &C);
    for (i = 0; i < R; ++i)
        for (j = 0; j < C-1; ++j)
            res = fscanf(f, "%d", &h[i][j]);
    for (i = 0; i < R-1; ++i)
        for (j = 0; j < C; ++j)
            res = fscanf(f, "%d", &v[i][j]);
    init(R, C, h, v);

    res = fscanf(f, "%d", &E);

    for (i = 0; i < E; i++) {
        res = fscanf(f, "%d", &event);
        if (event == 1) {
            res = fscanf(f, "%d%d%d", &P, &Q, &W);
            changeH(P, Q, W);
        } else if (event == 2) {
            res = fscanf(f, "%d%d%d", &P, &Q, &W);
            changeV(P, Q, W);
        } else if (event == 3) {
            res = fscanf(f, "%d%d", &V1, &V2);
            printf("%d\n", escape(V1, V2));
        } else
            fail("Invalid event type.");
    }
    cerr << "end\n";
    fclose(f);
    return 0;
}
#endif

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 'void build(int, int, int)':
wombats.cpp:83:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   83 |     int m = l + r >> 1;
      |             ~~^~~
wombats.cpp: In function 'void update(int, int, int, int)':
wombats.cpp:94:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   94 |     int m = l + r >> 1;
      |             ~~^~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 11092 KB Output is correct
2 Correct 6 ms 11092 KB Output is correct
3 Correct 71 ms 12888 KB Output is correct
4 Correct 5 ms 11092 KB Output is correct
5 Correct 5 ms 11092 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 468 KB Output is correct
8 Correct 1 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 64 ms 1548 KB Output is correct
12 Correct 1 ms 468 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 1880 KB Output is correct
2 Correct 87 ms 1788 KB Output is correct
3 Correct 121 ms 1828 KB Output is correct
4 Correct 110 ms 1816 KB Output is correct
5 Correct 104 ms 1788 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 457 ms 1812 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 12 ms 19564 KB Output is correct
2 Correct 9 ms 19540 KB Output is correct
3 Correct 10 ms 19540 KB Output is correct
4 Correct 41 ms 20328 KB Output is correct

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 97 ms 1748 KB Output is correct
2 Correct 88 ms 1748 KB Output is correct
3 Correct 101 ms 1808 KB Output is correct
4 Correct 107 ms 1820 KB Output is correct
5 Correct 104 ms 1772 KB Output is correct
6 Correct 11 ms 19540 KB Output is correct
7 Correct 10 ms 19544 KB Output is correct
8 Correct 10 ms 19624 KB Output is correct
9 Correct 42 ms 20348 KB Output is correct
10 Correct 6 ms 11092 KB Output is correct
11 Correct 6 ms 11092 KB Output is correct
12 Correct 78 ms 12964 KB Output is correct
13 Correct 6 ms 11092 KB Output is correct
14 Correct 5 ms 11092 KB Output is correct
15 Correct 0 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 468 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 468 KB Output is correct
23 Correct 1 ms 468 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 66 ms 1612 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 412 ms 1808 KB Output is correct
28 Correct 953 ms 76168 KB Output is correct
29 Correct 965 ms 62600 KB Output is correct
30 Correct 943 ms 62832 KB Output is correct
31 Correct 1016 ms 77528 KB Output is correct
32 Correct 1 ms 340 KB Output is correct

Subtask #6
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 1808 KB Output is correct
2 Correct 82 ms 1748 KB Output is correct
3 Correct 106 ms 1836 KB Output is correct
4 Correct 105 ms 1800 KB Output is correct
5 Correct 102 ms 1788 KB Output is correct
6 Correct 10 ms 19540 KB Output is correct
7 Correct 10 ms 19540 KB Output is correct
8 Correct 10 ms 19540 KB Output is correct
9 Correct 42 ms 20384 KB Output is correct
10 Correct 6 ms 11092 KB Output is correct
11 Correct 6 ms 11128 KB Output is correct
12 Correct 73 ms 12748 KB Output is correct
13 Correct 5 ms 11092 KB Output is correct
14 Correct 5 ms 11092 KB Output is correct
15 Correct 718 ms 124272 KB Output is correct
16 Correct 3700 ms 135064 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 1 ms 468 KB Output is correct
21 Correct 1 ms 468 KB Output is correct
22 Correct 1 ms 444 KB Output is correct
23 Correct 1 ms 448 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 1 ms 468 KB Output is correct
26 Correct 1 ms 468 KB Output is correct
27 Correct 67 ms 2800 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 439 ms 1880 KB Output is correct
30 Correct 957 ms 75832 KB Output is correct
31 Correct 3410 ms 132508 KB Output is correct
32 Correct 3401 ms 132552 KB Output is correct
33 Correct 963 ms 62564 KB Output is correct
34 Correct 3416 ms 109228 KB Output is correct
35 Correct 933 ms 62676 KB Output is correct
36 Correct 3424 ms 109588 KB Output is correct
37 Correct 1032 ms 77676 KB Output is correct
38 Correct 3590 ms 133084 KB Output is correct
39 Correct 1 ms 340 KB Output is correct
40 Correct 3434 ms 109760 KB Output is correct