Submission #1133635

#	Time	Username	Problem	Language	Result	Execution time	Memory
1133635		onlk97	Wiring (IOI17_wiring)	C++20	7 / 100	169 ms	327680 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
long long min_total_length(vector <int> r,vector <int> b){
    int n=r.size(),m=b.size();
    r.insert(r.begin(),0);
    b.insert(b.begin(),0);
    long long dp[n+1][m+1];
    for (int i=0; i<=n; i++){
        for (int j=0; j<=m; j++) dp[i][j]=1e18;
    }
    dp[0][0]=0;
    for (int i=0; i<n; i++){
        for (int j=0; j<=m; j++){
            long long sum=0;
            if (j) dp[i+1][j]=min(dp[i+1][j],dp[i][j]+abs(r[i+1]-b[j]));
            for (int k=j+1; k<=m; k++){
                sum+=abs(r[i+1]-b[k]);
                dp[i+1][k]=min(dp[i+1][k],dp[i][j]+sum);
            }
        }
    }
    return dp[n][m];
}

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