Submission #794306

#	Time	Username	Problem	Language	Result	Execution time	Memory
794306		TheSahib	Wiring (IOI17_wiring)	C++14	20 / 100	37 ms	13612 KiB

wiring

#include "wiring.h"
#include <bits/stdc++.h>

#define ll long long

using namespace std;

const int MAX = 1e3 + 5;

ll dp[MAX][MAX];

long long min_total_length(vector<int> r, vector<int> b) {
    if(b[0] > r[r.size() - 1]){
        if(r.size() < b.size()){
            swap(r, b);
            reverse(b.begin(), b.end());
        }
        int p1 = 0, p2 = 0;
        long long ans = 0;
        while(p1 != r.size() && p2 != b.size()){
            ans += abs(r[p1] - b[p2]);
            p1++;
            p2++;
        }
        while(p1 != r.size()){
            ans += min(abs(r[p1] - b[0]), abs(r[p1] - b.back()));
            p1++;
        }
        return ans;
    }
    
    for (int i = 0; i <= r.size(); i++)
    {
        dp[i][0] = 1e18;
    }
    for (int i = 0; i <= b.size(); i++)
    {
        dp[0][i] = 1e18;
    }
    dp[0][0] = 0;
    

    for (int i = 1; i <= r.size(); i++)
    {
        for (int j = 1; j <= b.size(); j++)
        {
            dp[i][j] = min(dp[i - 1][j - 1], min(dp[i - 1][j], dp[i][j - 1])) + abs(r[i - 1] - b[j - 1]);
        }
    }
    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:20:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         while(p1 != r.size() && p2 != b.size()){
      |               ~~~^~~~~~~~~~~
wiring.cpp:20:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |         while(p1 != r.size() && p2 != b.size()){
      |                                 ~~~^~~~~~~~~~~
wiring.cpp:25:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         while(p1 != r.size()){
      |               ~~~^~~~~~~~~~~
wiring.cpp:32:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for (int i = 0; i <= r.size(); i++)
      |                     ~~^~~~~~~~~~~
wiring.cpp:36:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for (int i = 0; i <= b.size(); i++)
      |                     ~~^~~~~~~~~~~
wiring.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i = 1; i <= r.size(); i++)
      |                     ~~^~~~~~~~~~~
wiring.cpp:45:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for (int j = 1; j <= b.size(); j++)
      |                         ~~^~~~~~~~~~~

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