Submission #1266581

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266581		coderg	Wiring (IOI17_wiring)	C++20	100 / 100	26 ms	10336 KiB

wiring

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll = long long;
const ll INF = 1e18;
//#include "wiring.h"
long long calc_score(ll num_back, ll num_front, ll sum_back, ll sum_front, ll max_back, ll min_front){
    return sum_front - sum_back - max(0LL, num_front-num_back)*max_back + max(0LL, num_back-num_front)*min_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<r.size() || bptr<b.size()){
        curblock.clear();
        while(bptr==b.size() || r[rptr]<b[bptr]){
            curblock.push_back(r[rptr++]);
            if (rptr==r.size()) break;
        }
        if (!curblock.empty()) blocks.push_back(curblock);
        if (bptr==b.size() && rptr==r.size()) break;
        curblock.clear();
        while(rptr==r.size() || b[bptr]<r[rptr]){
            curblock.push_back(b[bptr++]);
            if (bptr==b.size())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<blocks.size();++j){
        if (j==0) {
            for(int k=0;k<blocks[j].size();++k,++i) dp.push_back(INF);
            continue;
        }
        int cur_back=i-1;
        int sum_back=nums[cur_back];
        int far_back=i-blocks[j-1].size(); // no se puede ir mas lejos es esto
        int num_back=1;
        int num_front,sum_front = 0;
        int max_back=nums[i-1];
        int min_front=nums[i];
        for(int k=0;k<blocks[j].size();++k,++i){
            num_front=k+1; sum_front+=nums[i];
            ll best_score=min(dp[cur_back],dp[cur_back+1])+calc_score(num_back, num_front, sum_back, sum_front, max_back, min_front);
            // actualizar back
            while (cur_back > far_back){
                ll new_score = min(dp[cur_back-1],dp[cur_back])+calc_score(num_back+1, num_front, sum_back + nums[cur_back-1], sum_front, max_back, min_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: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 10 / 10
• Subtask 4: 25 / 25
• Subtask 5: 45 / 45