Submission #1264177

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264177		coderg	전선 연결 (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) (int)x.size()
const ll INF=1e18;

#include "wiring.h"
ll 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;
}

ll min_total_length(vector<signed> r,vector<signed> b){
    vector<vector<int>> blocks;
    vector<int> nums;
    int rptr=0,bptr=0;
    vector<int> currblock;
    while(rptr<sz(r) || bptr<sz(b)){
    currblock.clear();
    while(bptr==sz(b) || r[rptr]<b[bptr]){
        currblock.push_back(r[rptr++]);
        if(rptr==sz(r))break;
    }
    if(!currblock.empty())blocks.push_back(currblock);
    if(bptr==sz(b) && rptr==sz(r))break;
    currblock.clear();
    while(rptr==sz(r) || b[bptr]<r[rptr]){
        currblock.push_back(b[bptr++]);
        if(bptr==sz(b))break;
    }
    if(!currblock.empty())blocks.push_back(currblock);
    }
    for(auto block:blocks) for(auto x:block) nums.push_back(x);
    vector<ll> dp={0};//dp[i] = primeros 'i' contadores que se colocaron
    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 curr_back=i-1,sum_back=nums[curr_back],far_back=i-sz(blocks[j-1]),num_back=1;
        int num_front,sum_front=0,mx_back=nums[i-1],mn_front=nums[i];
       //no se puede ir más atrás que far_back

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

signed main(){
    int n,m;
    assert(2==scanf("%d %d",&n,&m));
    vector<int> 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]));
    }

    ll ans=min_total_length(r,b);
    printf("%lld\n",ans);
}
*/

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