oj.uz

Submission #1023862

# Submission time Handle Problem Language Result Execution time Memory
1023862 2024-07-15T08:00:51 Z Forested Wiring (IOI17_wiring) C++17
7 / 100
 1000 ms 13248 KB 
#include <bits/stdc++.h>
using namespace std;

using i32 = int;
using i64 = long long;
template <typename T>
using V = vector<T>;
template <typename T>
using VV = V<V<T>>;
template <typename T>
using VVV = V<V<V<T>>>;

#define OVERLOAD4(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32)(n); ++i)
#define REP3(i, l, r) for (i32 i = (i32)(l); i < (i32)(r); ++i)
#define REP(...) OVERLOAD4(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define PER2(i, n) for (i32 i = (i32)(n)-1; i >= 0; --i)
#define PER3(i, l, r) for (i32 i = (i32)(r)-1; i >= (i32)(l); --i)
#define PER(...) OVERLOAD4(__VA_ARGS__, PER3, PER2)(__VA_ARGS__)
#define ALL(x) begin(x), end(x)
#define LEN(x) (i32) size(x)

template <typename T>
bool chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}
template <typename T>
bool chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

void dbg(i32 x) { cerr << x; }
void dbg(i64 x) { cerr << x; }
template <typename T>
void dbg(const V<T> &arr) {
    cerr << "[";
    REP(i, LEN(arr)) {
        if (i) {
            cerr << ", ";
        }
        dbg(arr[i]);
    }
    cerr << "]";
}

void debug() {}
template <typename Head, typename... Tail>
void debug(const Head &head, const Tail &...tail) {
    dbg(head);
    if (sizeof...(Tail)) {
        cerr << ", ";
    } else {
        cerr << '\n';
    }
    debug(tail...);
}

#ifdef DEBUGF
#define DBG(...)                       \
    do {                               \
        cerr << #__VA_ARGS__ << " : "; \
        debug(__VA_ARGS__);            \
    } while (false)
#else
#define DBG(...) (void)0
#endif

#include "wiring.h"

constexpr i64 INF = 3003003003003003003;

i64 min_total_length(V<i32> r, V<i32> b) {
    i32 n = LEN(r), m = LEN(b);
    V<pair<i64, bool>> pts;
    {
        i32 rit = 0, bit = 0;
        while (LEN(pts) < n + m) {
            if (bit == m || (rit < n && r[rit] < b[bit])) {
                pts.emplace_back(r[rit++], false);
            } else {
                pts.emplace_back(b[bit++], true);
            }
        }
    }
    V<i64> dp(2 * (n + m) + 1, INF);
    dp[n + m] = 0;
    REP(i, n + m) {
        auto [x, b] = pts[i];
        V<i64> ndp(LEN(dp), INF);
        if (b) {
            REP(j, LEN(dp)) {
                REP(k, j) {
                    chmin(ndp[k], dp[j]);
                }
            }
        } else {
            REP(j, LEN(dp)) {
                REP(k, j + 1, LEN(dp)) {
                    chmin(ndp[k], dp[j]);
                }
            }
        }
        if (i != n + m - 1) {
            i64 nxt = pts[i + 1].first;
            REP(j, LEN(ndp)) {
                ndp[j] += abs(j - (n + m)) * (nxt - x);
            }
        }
        dp = ndp;
        DBG(dp);
    }
    i64 ans = dp[n + m];
    return ans;
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 79 ms 348 KB Output is correct
8 Correct 84 ms 348 KB Output is correct
9 Correct 88 ms 344 KB Output is correct
10 Correct 83 ms 344 KB Output is correct
11 Correct 86 ms 448 KB Output is correct
12 Correct 82 ms 600 KB Output is correct
13 Correct 82 ms 348 KB Output is correct
14 Correct 82 ms 344 KB Output is correct
15 Correct 100 ms 348 KB Output is correct
16 Correct 99 ms 444 KB Output is correct

Subtask #2
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 33 ms 348 KB Output is correct
3 Execution timed out 1063 ms 10212 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 600 KB Output is correct
3 Execution timed out 1057 ms 13248 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #4
0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Execution timed out 1036 ms 12704 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 79 ms 348 KB Output is correct
8 Correct 84 ms 348 KB Output is correct
9 Correct 88 ms 344 KB Output is correct
10 Correct 83 ms 344 KB Output is correct
11 Correct 86 ms 448 KB Output is correct
12 Correct 82 ms 600 KB Output is correct
13 Correct 82 ms 348 KB Output is correct
14 Correct 82 ms 344 KB Output is correct
15 Correct 100 ms 348 KB Output is correct
16 Correct 99 ms 444 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 33 ms 348 KB Output is correct
19 Execution timed out 1063 ms 10212 KB Time limit exceeded
20 Halted 0 ms 0 KB -