Submission #975146

#	Time	Username	Problem	Language	Result	Execution time	Memory
975146		LucaIlie	Wiring (IOI17_wiring)	C++17	100 / 100	54 ms	44272 KiB

wiring

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

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 ) {
#define int long long
    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 );

        }
    }


    return dp[seg.size() - 1].back();
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:30:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |     for ( int i = 0; i < a.size(); i++ )
      |                      ~~^~~~~~~~~~
wiring.cpp:32:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for ( int i = 0; i < b.size(); i++ )
      |                      ~~^~~~~~~~~~
wiring.cpp:45:26: warning: narrowing conversion of 'i' from 'long long int' to 'int' [-Wnarrowing]
   45 |         seg.push_back( { i, j } );
      |                          ^
wiring.cpp:45:29: warning: narrowing conversion of 'j' from 'long long int' to 'int' [-Wnarrowing]
   45 |         seg.push_back( { i, j } );
      |                             ^
wiring.cpp:49:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<segment>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   49 |     for ( int i = 0; i < seg.size(); i++ ) {
      |                      ~~^~~~~~~~~~~~
wiring.cpp:57:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<segment>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for ( int i = 1; i < seg.size(); i++ ) {
      |                      ~~^~~~~~~~~~~~
wiring.cpp:58: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]
   58 |         for ( int x = 0; x < dp[i - 1].size(); x++ ) {
      |                          ~~^~~~~~~~~~~~~~~~~~
wiring.cpp:66: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]
   66 |         for ( int x = 1; x < dp[i - 1].size(); x++ )
      |                          ~~^~~~~~~~~~~~~~~~~~
wiring.cpp:69: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]
   69 |         for ( int x = 0; x < dp[i].size(); x++ ) {
      |                          ~~^~~~~~~~~~~~~~
wiring.cpp:71: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]
   71 |                             (x >= dp[i - 1].size() ? INF : minSuf[i - 1][x] ) - wires[seg[i].l].x * x )
      |                              ~~^~~~~~~~~~~~~~~~~~~

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