Submission #599594

#	Time	Username	Problem	Language	Result	Execution time	Memory
599594		lcj	Wiring (IOI17_wiring)	C++17	17 / 100	1090 ms	47000 KiB

wiring

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

#define all(x) x.begin(), x.end()
#define fi first
#define se second

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;

vector<vector<int>> segments;
vector<int> dists;
vector<vector<ll>> precalcs;

ll explore(int idx, int inc);

void precalc(int idx) {
    auto &mS = segments[idx]; 
    int m = mS.size();
    vector<ll> tofront(m+1, 0); //0 to all
    for (int i = 1; i < m; i++)
    {
        tofront[i+1] = tofront[i];
        tofront[i+1] += mS[i] - mS[0];
    }
    vector<ll> toback(m+1, 0); //indexed by how many to front
    for (int i = m-2; i >= 0; i--)
    {
        toback[i] = toback[i+1];
        toback[i] += mS.back() - mS[i];
    }
    vector<ll> intcost(m+1, 0);
    for (int i = 0; i < m+1; i++)
    {
        intcost[i] = tofront[i] + toback[i];
    }
    vector<ll> tmcost(m+1, 1e15);
    for (int i = 0; i < m+1; i++)
    {
        if (idx == segments.size()-1 && i != m) continue;
        tmcost[i] = intcost[i] + (m-i) * dists[idx] + explore(idx+1, m-i);
    }
    precalcs[idx] = tmcost;
}

map<pii, ll> dp;

ll explore(int idx, int inc) {
    if (idx == segments.size()) return 0;
    if (precalcs[idx].empty()) precalc(idx);
    auto &mS = segments[idx]; 
    int m = mS.size();
    if (dp.count({idx, inc})) {
        return dp[{idx, inc}];
    }
    ll cmin = 1e15;
    for (int i = 0; i < m+1; i++)
    {
        if (idx == 0 && i != 0) continue;
        ll ccost = precalcs[idx][i] + (i-inc > 0 ? (i-inc) * dists[idx-1] : 0); 
        cmin = min(cmin, ccost);
    }
    dp[{idx, inc}] = cmin;
    return cmin;
}

ll min_total_length(vector<int> r, vector<int> b) {
    segments.clear();
    int fseg = *min_element(all(r)) > *min_element(all(b));
    vector<pii> items;
    for (auto i : r) {
        items.push_back({i, 0});
    }
    for (auto i : b) {
        items.push_back({i, 1});
    }
    sort(items.begin(), items.end());
    for (auto i : items) {
        if (!((segments.size() % 2) ^ fseg ^ i.se)) {
            segments.push_back({});
            
        }
        segments.back().push_back(i.fi);
    }
    int n = segments.size();
    for (int i = 0; i < n-1; i++)
    {
        dists.push_back(segments[i+1][0]-segments[i].back());
    }
    precalcs.assign(segments.size(), {});
    return explore(0, 0);
}

Compilation message (stderr)

wiring.cpp: In function 'void precalc(int)':
wiring.cpp:43:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |         if (idx == segments.size()-1 && i != m) continue;
      |             ~~~~^~~~~~~~~~~~~~~~~~~~
wiring.cpp: In function 'll explore(int, int)':
wiring.cpp:52:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |     if (idx == segments.size()) return 0;
      |         ~~~~^~~~~~~~~~~~~~~~~~

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