Submission #1264180

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264180		coderg	Wiring (IOI17_wiring)	C++20	0 / 100	23 ms	8956 KiB

wiring

/* 26.08.25 */
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define sz(x) x.size()
const ll INF=1e18;
#include "wiring.h"
long long calculate_score(ll num_back, ll num_front, ll sum_back, ll sum_front, ll mx_back, ll mn_front){
    return sum_front-sum_back-max(0LL,num_front-num_back)*mx_back+max(0LL,num_back-num_front)*mn_front;
}

long long min_total_length(vector<signed> r,vector<signed> b) {
    vector<vector<int>> blocks;
    vector<int> nums;
    int rptr=0,bptr=0;
    vector<int> curblock;
    while (rptr<sz(r) || bptr<sz(b)){
        curblock.clear();
        while(bptr==sz(b) || r[rptr]<b[bptr]){
            curblock.push_back(r[rptr++]);
            if (rptr==sz(r)) break;
        }
        if (!curblock.empty()) blocks.push_back(curblock);
        if (bptr==sz(b) && rptr==sz(r)) break;
        curblock.clear();

        while(rptr==sz(r) || b[bptr]<r[rptr]){
            curblock.push_back(b[bptr++]);
            if (bptr==sz(b)) break;

        }
        if (!curblock.empty()) blocks.push_back(curblock);
    }
    for(auto&block:blocks)for(auto&x:block)nums.push_back(x);
    vector<ll> dp={0}; // dp[i] = primeros 'i' contadores que ya han sido colocados
    int i=0;
    for(int j=0;j<sz(blocks);++j){
        if (j==0) {
            for(int k=0;k<sz(blocks[j]);++k,++i) dp.push_back(INF);
            continue;
        }
        int cur_back=i-1,sum_back=nums[cur_back];
        int far_back=i-sz(blocks[j-1]); //no se puede ir mas lejos es esto
        int num_back=1,num_front,sum_front=0;
        int mx_back=nums[i-1],mn_front=nums[i];

        for(int k=0;k<sz(blocks[j]);++k,++i){
            num_front=k+1;sum_front+=nums[i];
            ll best_score = dp[cur_back]+calculate_score(num_back,num_front,sum_back,sum_front,mx_back,mn_front);
            // actualizar back
            while (cur_back>far_back){
                ll new_score=dp[cur_back-1]+calculate_score(num_back+1,num_front,sum_back+nums[cur_back-1],sum_front,mx_back,mn_front);
                if (new_score<best_score || j==1){
                    best_score=new_score;
                    sum_back+=nums[cur_back - 1];
                    cur_back--;num_back++;
                }else break;
            }
            dp.push_back(best_score);
        }
    }
    return dp.back();
}

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