제출 #966594

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
966594		Amr	전선 연결 (IOI17_wiring)	C++17	25 / 100	19 ms	4952 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
#define sz size()
typedef long long ll;
#define all(x) (x).begin(),(x).end()
const int N = 2e5+2;
ll a[N];
long long min_total_length(std::vector<int> r, std::vector<int> b) {
    ll n = r.sz, m = b.sz;
    for(int i = 0; i < n; i++) a[r[i]] = 1;
    for(int i = 0; i < m; i++) a[b[i]] = 0;
    ll newlst = 0,start = 1,ans=0;
    for(int i = 1; i <= m+n; i++)
    {
        if(i==m+n||a[i+1]!=a[i])
        {
            ll en = i;
            ll lst = newlst; newlst = 0;
            for(int j = start; j <= en; j++)
            {
                ll d1 = j-start , d2 = en-j;
                if((start!=1)&&lst>0&&(d1<=d2||en==n+m))
                {
                    lst--;
                    ans+=d1;
                }
                else if((start!=1)&&lst==0&&(d1<d2||en==n+m))
                {
                    ans+=d1+1;
                }
                else
                {
                    newlst++;
                    ans+=d2+1;
                }
            }

            start = i+1;
        }
    }
    return ans;

}
// cases
//not start! lst > 0 and (d1<d2 or end)
//else notstart! lst == 0 (d1+1<D2 or end)
//else newlst++;

//cases:
//d1<d2
//d1+1<d2

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