Submission #783493

#	Time	Username	Problem	Language	Result	Execution time	Memory
783493		vjudge1	Wiring (IOI17_wiring)	C++17	0 / 100	379 ms	164932 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
    map<int, long long> dp[100100];
long long min_total_length(std::vector<int> R, std::vector<int> B) {
    for(int j = 1; j < 100100; j++)
        dp[j][0] = dp[0][j] = 1e18;
    int passed = 0;
    for(int i = 1; i <= R.size(); i++) {
        while(passed<B.size()&&B[passed]<R[i-1])
            passed++;
        for(int j = max(1, passed-10); j <= min((int)B.size(), passed+10); j++) {
            if(i==4&&j==4) {
                cout << "";
            }
            int dist1=1e9, dist2=1e9;
            auto y = lower_bound(B.begin(), B.begin()+j, R[i-1]);
            if(y!=B.begin()+j)
                dist1 = abs(*y-R[i-1]);
            if(y!=B.begin()) {
                y--;
                dist1 = min(dist1, abs(*y-R[i-1]));
            }
            auto x = lower_bound(R.begin(), R.begin()+i, B[j-1]);
            if(x!=R.begin()+i)
                dist2 = abs(*x-B[j-1]);
            if(x!=R.begin()) {
                x--;
                dist2 = min(dist2, abs(*x-B[j-1]));
            }
            dp[i][j] = min(dp[i-1][j-1]+abs(R[i-1]-B[j-1]), min(dp[i-1][j]+dist1, dp[i][j-1]+dist2));
        }
    }
	return dp[R.size()][B.size()];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:9:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    9 |     for(int i = 1; i <= R.size(); i++) {
      |                    ~~^~~~~~~~~~~
wiring.cpp:10:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 |         while(passed<B.size()&&B[passed]<R[i-1])
      |               ~~~~~~^~~~~~~~~

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