Submission #1166578

#	Time	Username	Problem	Language	Result	Execution time	Memory
1166578		Boycl07	Wiring (IOI17_wiring)	C++20	100 / 100	46 ms	7460 KiB

wiring

#include "wiring.h"
#include "bits/stdc++.h"

using namespace std;

#define ll long long
#define rep(i, n) for(int i = 1; i <= (n); ++i)
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define forn(i, l, r) for(int i = (l); (i) <= (r); ++i)
#define ford(i, r, l) for(int i = (r); (i) >= (l); --i)
#define endl "\n"
#define fi first
#define se second
#define pb push_back
#define pll pair<ll, ll>
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
#define sz(a) (int)(a.size())
#define task "note"

template<typename T> bool maximize(T &res, const T &val) {if(res < val) {res = val; return 1;} return 0;}
template<typename T> bool minimize(T &res, const T &val) {if(res < val) return 0; res = val; return 1;}
inline int readInt()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();int n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline ll readLong()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();ll  n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline string readString() {char c;while(c=getchar(),c==' '||c=='\n'||c=='\t');string s({c});while(c=getchar(),c!=EOF&&c!=' '&&c!='\n'&&c!='\t')s+=c;return s;}
const int N = 5000 + 3;
const int LOG = 12;
const int INF = 2e9;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
double get_cur_time() {return chrono::steady_clock::now().time_since_epoch().count();}



ll min_total_length(vector<int> r, vector<int> b)
{
    vector<pii> a;

    for(int x : r) a.pb({x, 0});
    for(int x : b) a.pb({x, 1});
    vector<int> dist(sz(a) + 1, INF);
    sort(all(a));
    for(int i = 1, lst = -1; i <= sz(a); ++i)
    {
        if(i > 1 && a[i - 1].se != a[i - 2].se) lst = i - 1;
        if(lst != -1) minimize(dist[i], abs(a[i - 1].fi - a[lst - 1].fi));
    }
    for(int i = sz(a), lst = -1; i >= 1; --i)
    {
        if(i < sz(a) && a[i - 1].se != a[i].se) lst = i + 1;
        if(lst != -1) minimize(dist[i], abs(a[i - 1].fi - a[lst - 1].fi));
    }
    vector<ll> pre(sz(a) + 1, 0);
    vector<ll> dp(sz(a) + 1, 0);
    for(int i = 1; i <= sz(a); ++i) pre[i] = pre[i - 1] + a[i - 1].fi;
    function<ll(int, int)> get_sum = [&](int l, int r) {
        return pre[r] - pre[l - 1];
    };
//    for(int i = 1; i <= sz(a); ++i)
//    {
//        cout << a[i - 1].fi << " " << a[i - 1].se << " " << dist[i] << endl;
//    }
    for(int i = 1, lst = 1; i <= sz(a); ++i)
    {
        int j = i;
        while(j <= sz(a) && a[j - 1].se == a[i - 1].se) ++j;
        --j;
        for(int k = i; k <= j; ++k)
        {
            dp[k] = dp[k - 1] + dist[k];
            int x = 2 * i - k - 1;
            if(x >= lst) minimize(dp[k], dp[x - 1] + get_sum(i, k) - get_sum(x, i - 1));
        }
        lst = i;
        i = j;
    }

    return dp[sz(a)];
}

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