Submission #1039634

#	Time	Username	Problem	Language	Result	Execution time	Memory
1039634		boyliguanhan	Wiring (IOI17_wiring)	C++17	100 / 100	43 ms	14920 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll ind[200100],rt[200100],lft[200100],prf[200100],col[200100],pos[200100],dp[200100];
ll cst(int l,int r){
    ll A=rt[l],B=lft[r];
    return ((A-l+1)*pos[A]-prf[A]+prf[l-1]+prf[r]-prf[B]-(r-B)*pos[B])+(pos[B]-pos[A])*max(A-l+1,r-B+1);
}
void dnc(int l,int r,int opl,int opr){
    if(!opl)return;
    if(l>r)return;
    int mid=l+r>>1,op=0;
    for(int i=opl;i<=opr;i++){
        ll K=min(dp[i-1],dp[i])+cst(i,mid);
        if(K<dp[mid]) op=i,dp[mid]=K;}
    dnc(l,mid-1,op,opr);
    dnc(mid+1,r,opl,op);
}
ll min_total_length(std::vector<int> r, std::vector<int> b) {
    int CC=0,n=r.size(),m=b.size();
    r.push_back(2e9);
    b.push_back(2e9);
    int lpt=0,rpt=0;
    for(int i=0;i<n+m;i++)
        if(r[lpt]<b[rpt]) pos[CC]=prf[++CC]=r[lpt++];
        else col[++CC]=1,pos[CC]=prf[CC]=b[rpt++];
    for(int i=1;i<=CC;i++)
        dp[i]=1e18;
    int BEF=0,c=col[1];
    int CC2=1;
    ind[1]=lft[1]=1;
    for(int i=2;i<=CC;i++){
        prf[i]+=prf[i-1];
        if(col[i]==c){
            ind[i]=ind[i-1];
            lft[i]=lft[i-1];
        } else {
            ind[i]=++CC2;
            lft[i]=i;
            for(int j=lft[i-1];j<i;j++)
                rt[j]=i-1;
            dnc(lft[i-1],rt[i-1],lft[BEF],rt[BEF]);
            BEF=i-1,c=col[i];
        }
    }
    dnc(lft[CC],CC,lft[BEF],rt[BEF]);
    return dp[CC];
}

Compilation message (stderr)

wiring.cpp: In function 'void dnc(int, int, int, int)':
wiring.cpp:13:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   13 |     int mid=l+r>>1,op=0;
      |             ~^~
wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:26:39: warning: operation on 'CC' may be undefined [-Wsequence-point]
   26 |         if(r[lpt]<b[rpt]) pos[CC]=prf[++CC]=r[lpt++];
      |                                       ^~~~

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