Submission #1264177

#TimeUsernameProblemLanguageResultExecution timeMemory
1264177codergWiring (IOI17_wiring)C++20
0 / 100
23 ms8956 KiB
/* 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); } */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...