Submission #717749

#	Time	Username	Problem	Language	Result	Execution time	Memory
717749		Jarif_Rahman	Wiring (IOI17_wiring)	C++17	100 / 100	80 ms	25216 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

const ll inf = 1e17;

ll min_total_length(vector<int> r, vector<int> b){
    vector<vector<ll>> v;
    int prev = -1;
    for(auto i = r.begin(), j = b.begin(); i != r.end() || j != b.end();){
        if(j == b.end() || (i != r.end() && *i < *j)){
            if(prev != 0) v.pb({});
            prev = 0;
            v.back().pb(*i);
            i++;
        }
        else{
            if(prev != 1) v.pb({});
            prev = 1;
            v.back().pb(*j);
            j++;
        }
    }

    int n = v.size();
    vector<vector<ll>> dp(n), pref(n), suff(n);
    vector<vector<ll>> mn1(n), mn2(n);

    for(int i = n-1; i >= 0; i--){
        int m = v[i].size();
        dp[i].assign(m, inf), pref[i].resize(m, 0), suff[i].resize(m, 0);
        mn1[i].assign(m, inf), mn2[i].assign(m, inf);

        for(int j = 0; j < m; j++){
            if(j) pref[i][j] = pref[i][j-1];
            pref[i][j]+=v[i][j];
        }
        for(int j = m-1; j >= 0; j--){
            if(j != m-1) suff[i][j] = suff[i][j+1];
            suff[i][j]+=v[i][j];
        }

        int k = v[i+1].size();

        for(int j = m-1; j >= 0; j--){
            if(i == n-1) continue;
            dp[i][j] = min(dp[i][j], v[i+1][0]*(m-j)-suff[i][j]+dp[i+1][0]);

            ll x = -suff[i][j];
            if(m-j-1 < k) x+=mn1[i+1][m-j-1]-(k-m+j)*v[i+1][0];
            else x+=mn1[i+1].back()+(m-j-k)*v[i+1][0];
            dp[i][j] = min(dp[i][j], x);

            if(m-j-1 < k) dp[i][j] = min(dp[i][j], mn2[i+1][m-j-1]-suff[i][j]+v[i][m-1]*(m-j));
        }

        if(i == 0) continue;
        for(int j = 0; j < m; j++){
            if(j) mn1[i][j] = mn1[i][j-1];
            ll cur = pref[i][j]+v[i][0]*(m-j-1);
            if(i == n-1 && j == m-1) mn1[i][j] = min(mn1[i][j], cur);
            else if(j == m-1) mn1[i][j] = min(mn1[i][j], cur+dp[i+1][0]);
            else mn1[i][j] = min(mn1[i][j], cur+dp[i][j+1]);
        }
        for(int j = m-1; j >= 0; j--){
            if(j != m-1) mn2[i][j] = mn2[i][j+1];
            ll cur = pref[i][j]-v[i-1].back()*(j+1);
            if(i == n-1 && j == m-1) mn2[i][j] = min(mn2[i][j], cur);
            else if(j == m-1) mn2[i][j] = min(mn2[i][j], cur+dp[i+1][0]);
            else mn2[i][j] = min(mn2[i][j], cur+dp[i][j+1]);
        }
    }

    return dp[0][0];
}

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