oj.uz

Submission #753979

# Submission time Handle Problem Language Result Execution time Memory
753979 2023-06-06T12:18:19 Z marvinthang Wombats (IOI13_wombats) C++17
55 / 100
 3676 ms 262144 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 = 5000;
const int MAX_C = 100;

int R, C, H[MAX_R][MAX_C], V[MAX_R][MAX_C];
int st[MAX_R << 2][MAX_C][MAX_C], opt[MAX_C][MAX_C];

void solve(int id, int r) {
    REP(x, C) {
        FOR(y, x + 1, C) st[id][x][y] = st[id][x][y - 1] + H[r][y - 1];
        REPD(y, x) st[id][x][y] = st[id][x][y + 1] + H[r][y];
    }
}

void pushUp(int id, int r) {
    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);
}

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

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

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.");
    }

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

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 27348 KB Output is correct
2 Correct 20 ms 27404 KB Output is correct
3 Correct 89 ms 29592 KB Output is correct
4 Correct 20 ms 27376 KB Output is correct
5 Correct 15 ms 27348 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 2 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 852 KB Output is correct
8 Correct 2 ms 696 KB Output is correct
9 Correct 1 ms 828 KB Output is correct
10 Correct 1 ms 724 KB Output is correct
11 Correct 84 ms 2404 KB Output is correct
12 Correct 1 ms 724 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 8500 KB Output is correct
2 Correct 37 ms 8388 KB Output is correct
3 Correct 62 ms 8572 KB Output is correct
4 Correct 54 ms 8532 KB Output is correct
5 Correct 53 ms 8528 KB Output is correct
6 Correct 1 ms 304 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 158 ms 8532 KB Output is correct
10 Correct 1 ms 308 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 57380 KB Output is correct
2 Correct 29 ms 57404 KB Output is correct
3 Correct 31 ms 57412 KB Output is correct
4 Correct 65 ms 58696 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 8624 KB Output is correct
2 Correct 49 ms 8480 KB Output is correct
3 Correct 57 ms 8576 KB Output is correct
4 Correct 54 ms 8480 KB Output is correct
5 Correct 51 ms 8564 KB Output is correct
6 Correct 28 ms 57316 KB Output is correct
7 Correct 37 ms 57388 KB Output is correct
8 Correct 31 ms 57404 KB Output is correct
9 Correct 69 ms 58812 KB Output is correct
10 Correct 15 ms 27348 KB Output is correct
11 Correct 15 ms 27348 KB Output is correct
12 Correct 83 ms 29644 KB Output is correct
13 Correct 15 ms 27348 KB Output is correct
14 Correct 15 ms 27348 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 724 KB Output is correct
19 Correct 1 ms 724 KB Output is correct
20 Correct 1 ms 816 KB Output is correct
21 Correct 1 ms 852 KB Output is correct
22 Correct 1 ms 724 KB Output is correct
23 Correct 1 ms 724 KB Output is correct
24 Correct 1 ms 724 KB Output is correct
25 Correct 71 ms 2448 KB Output is correct
26 Correct 1 ms 824 KB Output is correct
27 Correct 158 ms 8532 KB Output is correct
28 Runtime error 365 ms 262144 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 8500 KB Output is correct
2 Correct 38 ms 8492 KB Output is correct
3 Correct 65 ms 8580 KB Output is correct
4 Correct 54 ms 8532 KB Output is correct
5 Correct 56 ms 8532 KB Output is correct
6 Correct 33 ms 57420 KB Output is correct
7 Correct 32 ms 57420 KB Output is correct
8 Correct 31 ms 57440 KB Output is correct
9 Correct 63 ms 58768 KB Output is correct
10 Correct 17 ms 27384 KB Output is correct
11 Correct 17 ms 27416 KB Output is correct
12 Correct 96 ms 29752 KB Output is correct
13 Correct 20 ms 27348 KB Output is correct
14 Correct 15 ms 27372 KB Output is correct
15 Runtime error 3676 ms 186092 KB Execution killed with signal 11
16 Halted 0 ms 0 KB -