제출 #757115

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
757115		alexander707070	전선 연결 (IOI17_wiring)	C++14	7 / 100	1016 ms	176816 KiB

wiring

#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;

const long long inf=1e15;

int n,m,pt;
int red[MAXN],blue[MAXN];
int to[MAXN],to2[MAXN];

unordered_map<long long,bool> li;
unordered_map<long long,long long> dp;

long long st(long long x,long long y){
    return x*1000000+y;
}

int br(int l,int r){

}

long long ff(int l,int r){
    if(r>to[l] and n+m>500)return inf;
    if(l>to2[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];
    for(int i=1;i<=m;i++)blue[i]=B[i-1];

    for(int i=n+1;i<=n+10;i++)red[i]=inf;
    for(int i=m+1;i<=m+10;i++)blue[i]=inf;

    pt=1;
    for(int i=1;i<=n;i++){
        while(pt<m and blue[pt+1]<=red[i+8]){
            pt++;
        }
        to[i]=pt;
    }

    pt=1;
    for(int i=1;i<=m;i++){
        while(pt<n and red[pt+1]<=blue[i+8]){
            pt++;
        }
        to2[i]=pt;
    }

    return ff(1,1);
}

/*
int main(){
    cout<<min_total_length({1, 2, 3, 7}, {0, 4, 5, 9, 10})<<"\n";
}
*/

컴파일 시 표준 에러 (stderr) 메시지

wiring.cpp: In function 'int br(int, int)':
wiring.cpp:20:1: warning: no return statement in function returning non-void [-Wreturn-type]
   20 | }
      | ^
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:48:38: warning: overflow in conversion from 'long long int' to 'int' changes value from '1000000000000000' to '-1530494976' [-Woverflow]
   48 |     for(int i=n+1;i<=n+10;i++)red[i]=inf;
      |                                      ^~~
wiring.cpp:49:39: warning: overflow in conversion from 'long long int' to 'int' changes value from '1000000000000000' to '-1530494976' [-Woverflow]
   49 |     for(int i=m+1;i<=m+10;i++)blue[i]=inf;
      |                                       ^~~

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