Submission #757126

#	Time	Username	Problem	Language	Result	Execution time	Memory
757126		alexander707070	전선 연결 (IOI17_wiring)	C++14	20 / 100	41 ms	7480 KiB

wiring

#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;
 
const long long inf=1e15;
 
int n,m;
int red[MAXN],blue[MAXN];
long long raz[MAXN],zar[MAXN],ans;
 
unordered_map<long long,bool> li;
unordered_map<long long,long long> dp;
vector< pair<long long,int> > v;
 
long long st(long long x,long long y){
    return x*1000000+y;
}
 
long long ff(int l,int r){
    if(red[r]-blue[l]>raz[l] and n+m>500)return inf;
    if(blue[l]-red[r]>zar[r] and n+m>500)return inf;
 
    if(l==n and r==m)return abs(red[l]-blue[r]);
 
    if(li[st(l,r)])return dp[st(l,r)];
    li[st(l,r)]=true;
    dp[st(l,r)]=inf;
 
    if(l<n)dp[st(l,r)]=min(dp[st(l,r)],ff(l+1,r));
    if(r<m)dp[st(l,r)]=min(dp[st(l,r)],ff(l,r+1));
    if(l<n and r<m)dp[st(l,r)]=min(dp[st(l,r)],ff(l+1,r+1));
 
    dp[st(l,r)]+=abs(red[l]-blue[r]);
 
    return dp[st(l,r)];
}
 
long long min_total_length(vector<int> R,vector<int> B){
 
    n=int(R.size()); m=int(B.size());
 
    for(int i=1;i<=n;i++){
        red[i]=R[i-1];
        v.push_back({red[i],i});
    }
    for(int i=1;i<=m;i++){
        blue[i]=B[i-1];
        v.push_back({blue[i],n+i});
    }

    sort(v.begin(),v.end());

    for(int i=0;i<v.size();i++){
        if(v[i].second<=n){
            raz[v[i].second]=v[min(i+10,int(v.size())-1)].first-v[i].first;
        }else{
            zar[v[i].second-n]=v[min(i+10,int(v.size())-1)].first-v[i].first;
        }
    }

    if(n<=200 and m<=200){
        return ff(1,1);
    }else{
        if(n<=m){
            for(int i=1;i<=n;i++){
                ans+=blue[i]-red[i];
            }
            for(int i=n+1;i<=m;i++){
                ans+=blue[i]-red[n];
            }
        }else{
            for(int i=m;i>=1;i--){
                ans+=blue[i]-red[n-(m-i)];
            }
            for(int i=n-m;i>=1;i--){
                ans+=blue[1]-red[i];
            }
        }
        return ans;
    }
}
 
/*
int main(){
    cout<<min_total_length({1, 2, 3, 7}, {0, 4, 5, 9, 10})<<"\n";
}
*/

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:53:18: 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]
   53 |     for(int i=0;i<v.size();i++){
      |                 ~^~~~~~~~~

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