Submission #1097009

#	Time	Username	Problem	Language	Result	Execution time	Memory
1097009		lmToT27	Wiring (IOI17_wiring)	C++17	100 / 100	40 ms	10188 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
#define all(dataStructure) dataStructure.begin(),dataStructure.end()
#define ll long long
 
using namespace std;
namespace std {
        template <typename T, int D>
        struct _vector : public vector <_vector <T, D - 1>> {
                static_assert(D >= 1, "Dimension must be positive!");
                template <typename... Args>
                _vector(int n = 0, Args... args) : vector <_vector <T, D - 1>> (n, _vector <T, D - 1> (args...)) {}
        };
        // _vector <int, 3> a(n, m, k);: int a[n][m][k].
        // _vector <int, 3> a(n, m, k, x);: int a[n][m][k] initialized with x.
        template <typename T>
        struct _vector <T, 1> : public vector <T> {
                _vector(int n = 0, const T& val = T()) : vector <T> (n, val) {}
        };
}
 
const int MAX = 2e5 + 3;
const ll MOD[] = {1000000007, 998244353};
 
int n;
int last[2], cnt[MAX];
pair <int, int> x[MAX];
int cost[MAX];
ll dp[MAX];
ll prefix[MAX];
 
ll min_total_length(vector <int> a, vector <int> b) {
        x[0] = {-1, -1};
        for (int &i : a) x[++n] = make_pair(i, 0);
        for (int &i : b) x[++n] = make_pair(i, 1);
        sort(x + 1, x + n + 1);
        last[0] = last[1] = -1e9;
        for (int i = 1; i <= n; i++) {
                prefix[i] = prefix[i - 1] + x[i].first;
                cost[i] = x[i].first - last[x[i].second ^ 1];
                last[x[i].second] = x[i].first;
        }
        last[0] = last[1] = 2e9;
        for (int i = n; i >= 1; i--) {
                cost[i] = min(cost[i], last[x[i].second ^ 1] - x[i].first);
                last[x[i].second] = x[i].first;
        }
        for (int i = 1; i <= n; i++) {
                dp[i] = dp[i - 1] + cost[i];
                if (x[i].second == x[i - 1].second) cnt[i] = cnt[i - 1] + 1;
                else cnt[i] = 1;
                if (cnt[i] <= cnt[i - cnt[i]]) dp[i] = min(dp[i], dp[i - 2 * cnt[i]] + prefix[i] + prefix[i - 2 * cnt[i]] - 2 * prefix[i - cnt[i]]);
        }
        return dp[n];
}

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 45 / 45