| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 975145 | LucaIlie | Wiring (IOI17_wiring) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "wiring.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAX_N = 4e5;
const long long INF = 1e15;
struct wire {
int c, x;
};
struct segment {
int l, r;
};
long long sp[MAX_N + 1];
wire wires[MAX_N + 1];
vector<segment> seg;
vector<long long> dp[MAX_N + 1], minPref[MAX_N + 1], minSuf[MAX_N + 1];
long long sum( int l, int r ) {
return sp[r] - sp[l - 1];
}
long long min_total_length( vector<int> a, vector<int> b ) {
int n = a.size() + b.size();
for ( int i = 0; i < a.size(); i++ )
wires[i + 1] = { 0, a[i] };
for ( int i = 0; i < b.size(); i++ )
wires[i + 1 + a.size()] = { 1, b[i] };
sort( wires + 1, wires + 1 + n, []( wire x, wire y ) {
return x.x < y.x;
} );
for ( int i = 1; i <= n; i++ )
sp[i] = sp[i - 1] + wires[i].x;
int i = 1;
while ( i <= n ) {
int j = i;
while ( j + 1 <= n && wires[i].c == wires[j + 1].c )
j++;
seg.push_back( { i, j } );
i = j + 1;
}
for ( int i = 0; i < seg.size(); i++ ) {
dp[i].resize( seg[i].r - seg[i].l + 2 );
minPref[i].resize( seg[i].r - seg[i].l + 2 );
minSuf[i].resize( seg[i].r - seg[i].l + 2 );
}
for ( int x = 1; x <= seg[0].r - seg[0].l + 1; x++ )
dp[0][x] = INF;
for ( int i = 1; i < seg.size(); i++ ) {
for ( int x = 0; x < dp[i - 1].size(); x++ ) {
int z = seg[i - 1].r - seg[i - 1].l + 1 - x;
minPref[i - 1][z] = dp[i - 1][x] - sum( seg[i - 1].l + x, seg[i - 1].r ) + z * wires[seg[i - 1].r].x;
minSuf[i - 1][z] = dp[i - 1][x] - sum( seg[i - 1].l + x, seg[i - 1].r ) + z * wires[seg[i].l].x;
}
for ( int x = dp[i - 1].size() - 2; x >= 0; x-- )
minSuf[i - 1][x] = min( minSuf[i - 1][x], minSuf[i - 1][x + 1] );
for ( int x = 1; x < dp[i - 1].size(); x++ )
minPref[i - 1][x] = min( minPref[i - 1][x], minPref[i - 1][x - 1] );
for ( int x = 0; x < dp[i].size(); x++ ) {
dp[i][x] = min( (x == 0 ? INF : minPref[i - 1][min( x, (int)dp[i - 1].size()) - 1] - wires[seg[i - 1].r].x * x),
(x >= dp[i - 1].size() ? INF : minSuf[i - 1][x] ) - wires[seg[i].l].x * x )
+ sum( seg[i].l, seg[i].l + x - 1 );
/*if ( seg[i - 1].r - seg[i - 1].l + 1 - y < x )
cost += (long long)wires[seg[i - 1].r].x * (z - x);
else
cost += (long long)wires[seg[i].l].x * (z - x);*/
}
}
for ( int i = 0; i < seg.size(); i++ ) {
for ( int x = 0; x < dp[i].size(); x++ )
printf( "%lld ", dp[i][x] );
printf( "\n" );
}
return dp[seg.size() - 1].back();
}