Submission #617870

#	Time	Username	Problem	Language	Result	Execution time	Memory
617870		Sergio_2357	Wiring (IOI17_wiring)	C++17	0 / 100	1 ms	432 KiB

wiring

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

using namespace std;

#define int long long

#define F first
#define S second

typedef vector<int> vi;
typedef vector<vi> vii;
typedef vector<vii> viii;

int min_total_length(vector<signed> r, vector<signed> b)
{
    int res = 0;
    int n = r.size() + b.size();
    vector<pair<int, int>> a;
    for (int i = 0; i < r.size(); i++)
        a.push_back({ r[i], 0 });
    for (int i = 0; i < b.size(); i++)
        a.push_back({ b[i], 1 });
    sort(a.begin(), a.end());
    viii dp(n + 1, vii(r.size() + 2, vi(b.size() + 2, 1e18)));
    dp[0][0][0] = 0;
    int lst = 0;
    int lstr, lstb;
    lstr = lstb = -1e18;
    for (int i = 0; i < n; i++) {
        int d = a[i].F - lst;
        if (a[i].S == 0)
            lstr = a[i].F;
        else
            lstb = a[i].F;
        //cout << a[i].F << ' ' << a[i].S << ' ' << d << endl;
        for (int j = 0; j <= r.size(); j++) {
            for (int k = 0; k <= b.size(); k++) {
                if (a[i].S == 0) {
                    dp[i + 1][j][k] = min(dp[i][j][k] + (d * (j + k)) + (a[i].F - lstb), min(dp[i][j][k + 1] + (d * (j + k + 1)), (j > 0 ? dp[i][j - 1][k] + (d * (j + k - 1)) : (int)1e18)));
                } else {
                    dp[i + 1][j][k] = min(dp[i][j][k] + (d * (j + k)) + (a[i].F - lstr), min(dp[i][j + 1][k] + (d * (j + k + 1)), (k > 0 ? dp[i][j][k - 1] + (d * (j + k - 1)) : (int)1e18)));
                }
                //cout << dp[i + 1][j][k] << ' ';
            }
            //cout << endl;
        }
        //cout << endl
        //     << endl;
        lst = a[i].F;
    }
    return dp[n][0][0];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:20:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for (int i = 0; i < r.size(); i++)
      |                     ~~^~~~~~~~~~
wiring.cpp:22:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (int i = 0; i < b.size(); i++)
      |                     ~~^~~~~~~~~~
wiring.cpp:37:27: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |         for (int j = 0; j <= r.size(); j++) {
      |                         ~~^~~~~~~~~~~
wiring.cpp:38:31: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |             for (int k = 0; k <= b.size(); k++) {
      |                             ~~^~~~~~~~~~~
wiring.cpp:17:9: warning: unused variable 'res' [-Wunused-variable]
   17 |     int res = 0;
      |         ^~~

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