oj.uz

Submission #753929

# Submission time Handle Problem Language Result Execution time Memory
753929 2023-06-06T10:40:09 Z marvinthang Wombats (IOI13_wombats) C++17
55 / 100
 20000 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));
        REP(y, C) REP(k, C) minimize(st[id][x][k], st[id << 1][x][y] + V[r][y] + st[id << 1 | 1][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");
    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 14 ms 27348 KB Output is correct
3 Correct 77 ms 30236 KB Output is correct
4 Correct 14 ms 27456 KB Output is correct
5 Correct 15 ms 27348 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 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 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 724 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 2 ms 828 KB Output is correct
8 Correct 2 ms 724 KB Output is correct
9 Correct 1 ms 696 KB Output is correct
10 Correct 1 ms 692 KB Output is correct
11 Correct 65 ms 3184 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 871 ms 8556 KB Output is correct
2 Correct 894 ms 8432 KB Output is correct
3 Correct 851 ms 8644 KB Output is correct
4 Correct 871 ms 8536 KB Output is correct
5 Correct 903 ms 8524 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 3893 ms 8524 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #4
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 29 ms 57360 KB Output is correct
2 Correct 30 ms 57360 KB Output is correct
3 Correct 29 ms 57420 KB Output is correct
4 Correct 62 ms 58800 KB Output is correct

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 841 ms 8456 KB Output is correct
2 Correct 849 ms 8508 KB Output is correct
3 Correct 857 ms 8616 KB Output is correct
4 Correct 926 ms 8528 KB Output is correct
5 Correct 877 ms 8520 KB Output is correct
6 Correct 27 ms 57348 KB Output is correct
7 Correct 28 ms 57392 KB Output is correct
8 Correct 29 ms 57416 KB Output is correct
9 Correct 60 ms 58812 KB Output is correct
10 Correct 15 ms 27348 KB Output is correct
11 Correct 18 ms 27348 KB Output is correct
12 Correct 104 ms 30152 KB Output is correct
13 Correct 15 ms 27416 KB Output is correct
14 Correct 15 ms 27348 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 824 KB Output is correct
19 Correct 1 ms 724 KB Output is correct
20 Correct 1 ms 724 KB Output is correct
21 Correct 1 ms 724 KB Output is correct
22 Correct 2 ms 724 KB Output is correct
23 Correct 2 ms 724 KB Output is correct
24 Correct 2 ms 724 KB Output is correct
25 Correct 64 ms 3144 KB Output is correct
26 Correct 1 ms 724 KB Output is correct
27 Correct 3826 ms 8604 KB Output is correct
28 Runtime error 3673 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 860 ms 8452 KB Output is correct
2 Correct 819 ms 8440 KB Output is correct
3 Correct 853 ms 8536 KB Output is correct
4 Correct 855 ms 8588 KB Output is correct
5 Correct 851 ms 8540 KB Output is correct
6 Correct 30 ms 57420 KB Output is correct
7 Correct 30 ms 57384 KB Output is correct
8 Correct 29 ms 57420 KB Output is correct
9 Correct 62 ms 58780 KB Output is correct
10 Correct 15 ms 27348 KB Output is correct
11 Correct 15 ms 27460 KB Output is correct
12 Correct 80 ms 30192 KB Output is correct
13 Correct 15 ms 27416 KB Output is correct
14 Correct 14 ms 27376 KB Output is correct
15 Execution timed out 20007 ms 26272 KB Time limit exceeded
16 Halted 0 ms 0 KB -