Submission #433193

#	Time	Username	Problem	Language	Result	Execution time	Memory
433193		pliam	Wiring (IOI17_wiring)	C++14	0 / 100	1080 ms	8604 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define MAXN 100005
#define MAXM 100005
#define INF (ll)2e18

vector<pair<ll,int>> points;//0=red,1=blue
ll dp[MAXN+MAXM];
ll suff[MAXN],pref,dist;
int pos;
int size_seg;
int m;

ll min_total_length(vector<int> r, vector<int> b) {
    points.push_back({-1,-1});
    for(auto x:r){
        points.push_back({x,0});
    }
    for(auto x:b){
        points.push_back({x,1});
    }
    sort(points.begin(),points.end());
    pos=1;
    m=1;
    dp[0]=0;
    dp[1]=INF;
    while(points[pos].second==points[pos+1].second){
        dp[pos+1]=INF;
        pos++;
        m++;
    }
    pos++;
    m++;
    while(pos<points.size()){
        if(points[pos].second!=points[pos-1].second){
            //new segment
            size_seg=m-1;
            m=1;
            suff[0]=0;
            pref=0;
            for(int i=1;i<=size_seg;i++){
                suff[i]=suff[i-1]+points[pos-1].first-points[pos-i].first;
            }
            dist=points[pos].first-points[pos-1].first;
        }else{
            pref+=points[pos].first-points[pos-m+1].first;
        }
        dp[pos]=INF;
        for(int n=1;n<=size_seg;n++){
            dp[pos]=min(dp[pos],dp[pos-m-n]+pref+suff[n]+max(m,n)*dist);
        }
        m++;
        pos++;
    }
    return dp[points.size()-1];
}

Compilation message (stderr)

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:36:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     while(pos<points.size()){
      |           ~~~^~~~~~~~~~~~~~

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