#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();
}
Compilation message
wiring.cpp: In function 'long long int min_total_length(std::vector<long long int>, std::vector<long long int>)':
wiring.cpp:31:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
31 | for ( int i = 0; i < a.size(); i++ )
| ~~^~~~~~~~~~
wiring.cpp:33:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | for ( int i = 0; i < b.size(); i++ )
| ~~^~~~~~~~~~
wiring.cpp:50:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<segment>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
50 | for ( int i = 0; i < seg.size(); i++ ) {
| ~~^~~~~~~~~~~~
wiring.cpp:58:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<segment>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
58 | for ( int i = 1; i < seg.size(); i++ ) {
| ~~^~~~~~~~~~~~
wiring.cpp:59:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
59 | for ( int x = 0; x < dp[i - 1].size(); x++ ) {
| ~~^~~~~~~~~~~~~~~~~~
wiring.cpp:67:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
67 | for ( int x = 1; x < dp[i - 1].size(); x++ )
| ~~^~~~~~~~~~~~~~~~~~
wiring.cpp:70:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | for ( int x = 0; x < dp[i].size(); x++ ) {
| ~~^~~~~~~~~~~~~~
wiring.cpp:72:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
72 | (x >= dp[i - 1].size() ? INF : minSuf[i - 1][x] ) - wires[seg[i].l].x * x )
| ~~^~~~~~~~~~~~~~~~~~~
wiring.cpp:84:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<segment>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
84 | for ( int i = 0; i < seg.size(); i++ ) {
| ~~^~~~~~~~~~~~
wiring.cpp:85:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
85 | for ( int x = 0; x < dp[i].size(); x++ )
| ~~^~~~~~~~~~~~~~
/usr/bin/ld: /tmp/cc387Wpm.o: in function `main':
grader.cpp:(.text.startup+0x23a): undefined reference to `min_total_length(std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status
