제출 #578005

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
578005		AugustinasJucas	전선 연결 (IOI17_wiring)	C++14	0 / 100	1092 ms	8588 KiB

wiring

#include <bits/stdc++.h>
using namespace std;
#include "wiring.h"
int n;
const long long inf = 1e18;
vector<int> groupInd;
vector<pair<int, int> > interv;
vector<pair<int, int> > groups;
    
long long f(int l, int r) {
    
    int prm = groups[l].second;
    int ant = groups[r].second;
    int kekL = 0, kekR = 0;
    int maxL = 0, minR = 1e9;
    long long sumL = 0, sumR = 0;
    for(int i = l; i <= r; i++) {
        kekL += (groups[i].second == prm);
        kekR += (groups[i].second == ant);
        if(groups[i].second == prm) {
            sumL += groups[i].first;
            maxL = max(maxL, groups[i].first);
        }else {
            sumR += groups[i].first;
            minR = min(minR, groups[i].first);
        }
    }
    long long ret = 0;
    ret += kekL * maxL - sumL;
    ret += sumR - kekR * minR;
    ret += (minR - maxL) * max(kekL, kekR);
    return ret;

}
long long min_total_length(vector<int> r, vector<int> b) {
    n = r.size() + b.size();
    for(auto &x : r) {
        groups.push_back({x, 0});
    }
    for(auto &x : b) {
        groups.push_back({x, 1});
    }
    groupInd.resize(n);

    sort(groups.begin(), groups.end());
    for(int i = 0; i < n; i++) {
        for(int j = i; j <= n; j++) {
            if(j == n || groups[j].second != groups[i].second) {
                int l = i;
                int r = j-1;

                interv.push_back({l, r});
                for(int h = l; h <= r; h++) {
                    groupInd[h] = (int) interv.size()-1;
                }
                i = j-1;
                break;
            }
        }
    } /*
    cout << "intervalai: ";
    for(auto &x : interv) {
        cout << "(" << x.first << ", " << x.second << "), ";
    }
    cout << endl;*/
    vector<long long> dp(n, inf);
    // dp[-1] = 0;    
    
    for(int i = interv[1].first; i < n; i++) {
        int myInterv = groupInd[i];
        for(int j = interv[myInterv-1].first; j <= interv[myInterv-1].second; j++) {
            
            dp[i] = min(dp[i], (j == 0 ? 0ll : dp[j-1]) + f(j, i));

        } 

    } 

    
    return dp[n-1];
}

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