제출 #575037

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
575037		Lobo	전선 연결 (IOI17_wiring)	C++17	100 / 100	61 ms	14760 KiB

wiring

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

const long long inf = (long long) 1e18 + 10;
const int inf1 = (int) 1e9 + 10;
#define int long long
#define dbl long double
#define endl '\n'
#define sc second
#define fr first
#define mp make_pair
#define pb push_back
#define all(x) x.begin(), x.end()

const int maxn = 2e5+10;

int n, m, pf[maxn], pfmn[maxn], sfmn[maxn], val[maxn];

int min_total_length(std::vector<int32_t> r, std::vector<int32_t> b) {
    n = r.size();
    m = b.size();
    vector<pair<int,int>> cn;
    for(auto x : r) cn.pb(mp(x,0));
    for(auto x : b) cn.pb(mp(x,1));
    n+= m;
    sort(all(cn));
    for(int i = 0; i < n; i++) {
        if(i != 0) pf[i]+= pf[i-1];
        pf[i]+= cn[i].fr;
    }

    int L = n,R = n;
    vector<int> dp(n+1);
    dp[n] = 0;
    int k;
    for(int i = n-1; i >= 0; i--) {
        if(i != n-1 && cn[i].sc != cn[i+1].sc) {
            R = L-1;
            L = i+1;
            k = i;
            for(int j = L; j <= R; j++) {
                val[j] = pf[j]-pf[k] - (j-k)*cn[k+1].fr;
            }

            //prefix that we have more R than B
            for(int j = L; j <= R; j++) {
                if(j == L) pfmn[j] = inf;
                else pfmn[j] = pfmn[j-1];

                pfmn[j] = min(pfmn[j],val[j]+min(dp[j+1],dp[j]));
            }
            for(int j = R; j >= L; j--) {
                if(j == R) sfmn[j] = inf;
                else sfmn[j] = sfmn[j+1];
                
                sfmn[j] = min(sfmn[j],val[j]+min(dp[j+1],dp[j]) + (cn[k+1].fr-cn[k].fr)*(j-k));
            }
        }
        if(L == n) {
            dp[i] = inf;
            continue;
        }
        

        int p = 2*k-i+1;
        p = min(p,R);
        //vejo os j <= p
        int cons = (k-i+1)*cn[k].fr -pf[k] + (i != 0 ? pf[i-1] : 0);

        dp[i] = pfmn[p]+cons+(k-i+1)*(cn[k+1].fr-cn[k].fr);
        if(p != R) dp[i] = min(dp[i],sfmn[p+1]+cons);
        // cout << i << " = " << dp[i] << endl;
    }

    return dp[0];
}

// int32_t main() {
//     ios::sync_with_stdio(false); cin.tie(0);

//     freopen("in.in", "r", stdin);
    
//     int32_t N, M;
//     assert(2 == scanf("%d %d", &N, &M));

//     vector<int32_t> r(N), b(M);
//     for(int i = 0; i < N; i++)
//         assert(1 == scanf("%d", &r[i]));
//     for(int i = 0; i < M; i++)
//         assert(1 == scanf("%d", &b[i]));

//     long long res = min_total_length(r, b);
//     printf("%lld\n", res);
//     return 0;

// }

컴파일 시 표준 에러 (stderr) 메시지

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:66:18: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
   66 |         int p = 2*k-i+1;
      |                 ~^~

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