Submission #717739

#	Time	Username	Problem	Language	Result	Execution time	Memory
717739		Jarif_Rahman	Wiring (IOI17_wiring)	C++17	17 / 100	1069 ms	21136 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);

    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);

        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);

            for(int l = 0; l < k; l++){
                ll cur = pref[i+1][l]-suff[i][j];
                if(m-j > l+1) continue; //cur+=v[i+1][0]*(m-j-l-1);
                else cur-=v[i][m-1]*(l+1-m+j);

                if(i+1 == n-1 && l == k-1) dp[i][j] = min(dp[i][j], cur);
                else if(l == k-1) dp[i][j] = min(dp[i][j], cur+dp[i+2][0]);
                else dp[i][j] = min(dp[i][j], cur+dp[i+1][l+1]);
            }
        }

        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]);
        }
    }

    return dp[0][0];
}

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