Submission #165118

#	Time	Username	Problem	Language	Result	Execution time	Memory
165118		Segtree	Wiring (IOI17_wiring)	C++14	7 / 100	42 ms	6264 KiB

wiring

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<set>
#include<unordered_map>
#include"wiring.h"
using namespace std;
typedef long long ll;
#define chmax(a,b) a=max(a,b)
#define chmin(a,b) a=min(a,b)
#define mod 1000000007
#define mad(a,b) a=(a+b)%mod
#define N 210
ll min_total_length(vector<int> a,vector<int> b){
    ll dp[N][N];
    for(int i=0;i<a.size();i++)for(int j=0;j<b.size();j++){
	dp[i][j]=1e17;
    }
    dp[0][0]=abs(a[0]-b[0]);
    for(int i=0;i<a.size();i++){
	for(int j=0;j<b.size();j++){
	    bool vl=i<a.size()-1,vr=j<b.size()-1;
	    if(vl)chmin(dp[i+1][j],dp[i][j]+abs(a[i+1]-b[j]));
	    if(vr)chmin(dp[i][j+1],dp[i][j]+abs(a[i]-b[j+1]));
	    if(vl&vr){
		chmin(dp[i+1][j+1],dp[i][j]+abs(a[i+1]-b[j+1]));
	    }
	}
    }
    /*
    for(int i=0;i<a.size();i++){
	for(int j=0;j<b.size();j++){
	    cout<<dp[i][j]<<" ";
	}
	cout<<endl;
    }*/
    return dp[a.size()-1][b.size()-1];
}
/*
int main(){
    cin.tie(0);
    ios::sync_with_stdio(0);
    vector<ll> a,b;
    ll n,m; cin>>n>>m;
    for(int i=0;i<n;i++){
	ll x; cin>>x;
	a.push_back(x);
    }
    for(int i=0;i<m;i++){
	ll x; cin>>x;
	b.push_back(x);
    }
    cout<<min_total_length(a,b)<<endl;
}*/

Compilation message (stderr)

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:17:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<a.size();i++)for(int j=0;j<b.size();j++){
                 ~^~~~~~~~~
wiring.cpp:17:45: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<a.size();i++)for(int j=0;j<b.size();j++){
                                            ~^~~~~~~~~
wiring.cpp:21:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<a.size();i++){
                 ~^~~~~~~~~
wiring.cpp:22:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int j=0;j<b.size();j++){
              ~^~~~~~~~~
wiring.cpp:23:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      bool vl=i<a.size()-1,vr=j<b.size()-1;
              ~^~~~~~~~~~~
wiring.cpp:23:31: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
      bool vl=i<a.size()-1,vr=j<b.size()-1;
                              ~^~~~~~~~~~~

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