Submission #738427

#	Time	Username	Problem	Language	Result	Execution time	Memory
738427		Elvin_Fritl	Wiring (IOI17_wiring)	C++17	0 / 100	1086 ms	980 KiB

wiring

#include <bits/stdc++.h>
using namespace std;
#include "wiring.h"

const int MX=1e5+5;

long long min_total_length(vector<int> r, vector<int> b){
    vector<int>v(2e5+5,0);

    for(int i=0;i<(int)r.size();i++){
        v[r[i]]=1;
    }

    int say=0,n=(int)r.size() + (int)b.size();

    vector<int>tt;

    for(int i=0;i<=n;i++){
        if(i==0 || v[i]==v[i-1]){
            say++;
        }
        else{
            tt.push_back(say);
            say=1;
        }
    }

    tt.push_back(say);

    long long res=0;

    int j=1,i=0;

    while(i<j && j<n){
        if(tt[i]==0){
            continue;
        }
        int tmp=min(tt[i],tt[j]);
        res+=(tmp*tmp);
        tt[i]-=tmp;
        tt[j]-=tmp;
        if(tt[i]==0){
            i++;
        }
        if(tt[j]==0){
            j++;
        }
    }

    return res;
}

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