oj.uz

Submission #786592

# Submission time Handle Problem Language Result Execution time Memory
786592 2023-07-18T09:46:08 Z drdilyor Wombats (IOI13_wombats) C++17
28 / 100
 3020 ms 16228 KB 
#include<bits/stdc++.h>
#include "wombats.h"
using namespace std;
const int inf = 1e9;
using ll = long long;
constexpr ll infl = 1e18;

struct SegmentTree {
    using T = ll;
    using S = ll;
    const T id = infl;
    inline T single(S v) { return v; }

    T merge(const T& l, const T& r) {
        return min(l, r);
    }

    int n;
    vector<T> tree;

    SegmentTree(int n) : n(n) {
        tree.resize(n * 2, id);
        build();
    }
    SegmentTree(vector<S> arr) : n(arr.size()) {
        tree.resize(n * 2, id);
        for (int i = 0; i < n; i++) {
            tree[i + n] = single(arr[i]);
        }
        build();
    }

    void build() {
        for (int i = n-1; i >= 1; i--) {
            tree[i] = merge(tree[i*2], tree[i*2 + 1]);
        }
    }

    void update(int i, S v) {
        tree[i+=n] = single(v);
        for (i /= 2; i >= 1; i/= 2)
            tree[i] = merge(tree[i*2], tree[i*2+1]);
    }

    T query(int l, int r) {
        T left = id, right = id;
        l += n;
        r += n;
        while (l <= r) {
            if (l % 2 == 1) left = merge(left, tree[l++]);
            if (r % 2 == 0) right = merge(right, tree[r--]);
            l /= 2; r /= 2;
        }
        return merge(left, right);
    }

    int find_first(function<bool(T&)> predicate, int last = 0) {
        int v = 1;
        while (v < n) {
            if (predicate(tree[v*2 + last])) v = v*2 + last;
            else if (predicate(tree[v*2 + !last])) v = v*2 + !last;
            else return -1;
        }
        return v;
    }
};


int r, c;
vector<vector<int>> level;
vector<vector<int>> pass;
vector<vector<ll>> dist;

vector<int> dirty;

void update(int v2) {
    if (!dirty[v2]) return;
    dirty[v2] = 1;

    vector<ll> dp(c, infl);
    dp[v2] = 0;
    for (int i = r-1; i >= 0; i--) {

        auto sum = [&](int r) {
            ll s = 0;
            for (int j = 0; j <= r; j++)
                s += level[i][j];
            return s;
        };

        vector<ll> ndp(c, infl);
        SegmentTree st(c);

        for (int j = 0; j < c; j++) {
            ll mn = st.query(0, j-1);
            ndp[j] = mn + sum(j-1);
            st.update(j, dp[j] - sum(j - 1));
        }

        for (int j = 0; j < c; j++) {
            for (ll k = j, sum = 0; k < c; k++) {
                ndp[j] = min(ndp[j], dp[k] + sum);
                if (k < c-1) sum += level[i][k];
            }
        }

        for (int j = 0; j < c; j++) {
            if (i) ndp[j] += pass[i-1][j];
        }

        dp.swap(ndp);
    }
    for (int v1 = 0; v1 < c; v1++)
        dist[v1][v2] = dp[v1];
}

void init(int r, int c, int h[5000][200], int v[5000][200]) {
    assert((r <= 100 && c <= 100));
    ::r = r;
    ::c = c;
    level.resize(r);
    for (int i = 0; i < r; i++) {
        level[i].resize(c-1);
        for (int j = 0; j < c-1; j++) {
            level[i][j] = h[i][j];
        }
    }

    pass.resize(r-1);
    for (int i = 0; i < r-1; i++) {
        pass[i].resize(c);
        for (int j = 0; j < c; j++) {
            pass[i][j] = v[i][j];
        }
    }
    dirty.assign(c, 1);
    dist = vector(c, vector(c, 0ll));
}

void changeH(int p, int q, int w) {
    level[p][q] = w;
    dirty.assign(c, 1);
}

void changeV(int p, int q, int w) {
    pass[p][q] = w;
    dirty.assign(c, 1);
}

int escape(int v1, int v2) {
    update(v2);
    return dist[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 Runtime error 6 ms 8404 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 7 ms 340 KB Output is correct
5 Correct 7 ms 340 KB Output is correct
6 Correct 6 ms 340 KB Output is correct
7 Correct 7 ms 340 KB Output is correct
8 Correct 5 ms 340 KB Output is correct
9 Correct 6 ms 340 KB Output is correct
10 Correct 6 ms 340 KB Output is correct
11 Correct 3020 ms 1304 KB Output is correct
12 Correct 7 ms 340 KB Output is correct

Subtask #3
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 136 ms 624 KB Output is correct
2 Correct 134 ms 640 KB Output is correct
3 Correct 145 ms 596 KB Output is correct
4 Correct 168 ms 596 KB Output is correct
5 Correct 140 ms 596 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 142 ms 624 KB Output is correct
10 Correct 0 ms 212 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 16228 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 142 ms 624 KB Output is correct
2 Correct 161 ms 640 KB Output is correct
3 Correct 149 ms 624 KB Output is correct
4 Correct 139 ms 624 KB Output is correct
5 Correct 158 ms 596 KB Output is correct
6 Runtime error 10 ms 16212 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -

Subtask #6
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 596 KB Output is correct
2 Correct 152 ms 616 KB Output is correct
3 Correct 145 ms 620 KB Output is correct
4 Correct 155 ms 620 KB Output is correct
5 Correct 137 ms 624 KB Output is correct
6 Runtime error 13 ms 16212 KB Execution killed with signal 6
7 Halted 0 ms 0 KB -