제출 #899886

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
899886		nightfal	Wiring (IOI17_wiring)	C++14	100 / 100	26 ms	5200 KiB

wiring

#include <cassert>
#include <cstdio>
#include <vector>
#include <climits>
#include <stdlib.h>
#include <algorithm>
using namespace std;
 
long long min_total_length(std::vector<int> r, std::vector<int> b) {
    int n = r.size(), m = b.size();
    vector<pair<int,int>> a(n+m);
    
    for(int i=0, j=0; i<n || j<m;)
        i==n? a[i+j++]=make_pair(j,1): j==m? a[j+i++]=make_pair(i,0): r[i]<b[j]? a[j+i++]=make_pair(i,0): a[i+j++]=make_pair(j,1);

    vector<long long> dp(n+m,LLONG_MAX);

    long long sumL=0, cntL=0, sumR=0, cntR=0, gap=0;
    int prev=-1, curr=0, optIdx=0;

    for(int i=1; i<n+m; i++) {
        if (a[i].second != a[i-1].second) {
            prev=curr; curr=i; sumR=cntR=0; sumL=0; optIdx=curr-1;
            gap= a[prev].second==0? b[a[curr].first]-r[a[curr-1].first]: r[a[curr].first]-b[a[curr-1].first];
        }

        if (prev==-1) continue;

        sumR += a[curr].second==0? r[a[i].first]-r[a[curr].first]:b[a[i].first]-b[a[curr].first];
        cntR++;

        for(int j=optIdx; j>=prev; j--) {
            cntL=curr-j; 
            sumL += a[prev].second==0? r[a[curr-1].first]-r[a[j].first]:b[a[curr-1].first]-b[a[j].first]; 
            long long temp = sumL + sumR + max(cntL,cntR)*gap;
            if (j==0) {dp[i] = min(dp[i],temp); optIdx = 0;}
            else {
                long long minDP = min(dp[j-1],dp[j]);        
                if (minDP == LLONG_MAX) continue;
                else temp += minDP;                    
                if (dp[i]>temp) {dp[i]=temp;optIdx=j;}
                else break;
            }
        }
        for(int k=max(optIdx-1,prev); k<=optIdx; k++)
            sumL -= a[prev].second==0? r[a[curr-1].first]-r[a[k].first]:b[a[curr-1].first]-b[a[k].first]; 
    }
    return dp[n+m-1];
}

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