Submission #1014231

#	Time	Username	Problem	Language	Result	Execution time	Memory
1014231		ThegeekKnight16	Wiring (IOI17_wiring)	C++17	100 / 100	29 ms	10284 KiB

wiring

#include <bits/stdc++.h>
#include "wiring.h"
using namespace std;
typedef long long ll;
const ll INF = 0x3f3f3f3f3f3f3f3f;

long long min_total_length(std::vector<int> r, std::vector<int> b)
{
    int N = r.size(), M = b.size();
    vector<vector<ll>> v;
    int lastType = -1;
    int p = 0, q = 0;
    while (p < N && q < M)
    {
        if (r[p] < b[q])
        {
            if (lastType == 0) v.back().push_back(r[p++]);
            else v.push_back({r[p++]});
            lastType = 0;
        }
        else
        {
            if (lastType == 1) v.back().push_back(b[q++]);
            else v.push_back({b[q++]});
            lastType = 1;
        }
    }
    while (p < N)
    {
        if (lastType == 0) v.back().push_back(r[p++]);
        else v.push_back({r[p++]});
        lastType = 0;
    }
    while (q < M)
    {
        if (lastType == 1) v.back().push_back(b[q++]);
        else v.push_back({b[q++]});
        lastType = 1;
    }

    vector<vector<ll>> dp(v.size());
    dp[0].resize(v[0].size()+1, INF); dp[0].back() = -accumulate(v[0].begin(), v[0].end(), 0LL);
    for (int i = 1; i < v.size(); i++)
    {
        int n = v[i].size(), m = v[i-1].size();
        vector<ll> pref(m+1), suf(m+1);
        pref[0] = dp[i-1][0];
        for (int j = 1; j <= m; j++) pref[j] = min(dp[i-1][j], pref[j-1]-v[i-1].back());
        suf.back() = dp[i-1].back();
        for (int j = m-1; j >= 0; j--) suf[j] = min(dp[i-1][j], suf[j+1]+v[i][0]);

        dp[i].resize(n+1, INF);
        ll sum = -accumulate(v[i].begin(), v[i].end(), 0LL);
        dp[i][0] = sum + min(pref[0], suf[0]);
        for (int j = 1; j <= n; j++)
        {
            sum += 2*v[i][j-1];
            if (j > m) dp[i][j] = sum + pref.back() - (j-m)*v[i-1].back();
            else dp[i][j] = sum + min(pref[j], suf[j]);
        }
        reverse(dp[i].begin(), dp[i].end());
    }

    return dp.back()[0];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i = 1; i < v.size(); i++)
      |                     ~~^~~~~~~~~~

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