Submission #46947

#	Time	Username	Problem	Language	Result	Execution time	Memory
46947		SpaimaCarpatilor	Wiring (IOI17_wiring)	C++17	17 / 100	1080 ms	26612 KiB

wiring

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

using namespace std;

int N, x[200009], col[200009], minD[200009];
long long dp[200009], s[200009];
const int INF = 1e9 + 100;

void init (vector < int > &rr, vector < int > &bb)
{
    int pntr1 = 0, pntr2 = 0;
    while (pntr1 < rr.size () || pntr2 < bb.size ())
    {
        if (pntr2 == bb.size () || (pntr1 < rr.size () && rr[pntr1] < bb[pntr2]))
            x[++N] = rr[pntr1], pntr1 ++, col[N] = 0;
        else
            x[++N] = bb[pntr2], pntr2 ++, col[N] = 1;
    }
    int lst[2];
    lst[0] = lst[1] = -1;
    for (int i=1; i<=N; i++)
    {
        if (lst[col[i] ^ 1] == -1) minD[i] = INF;
        else minD[i] = x[i] - lst[col[i] ^ 1];
        lst[col[i]] = x[i];
    }
    lst[0] = lst[1] = -1;
    for (int i=N; i>=1; i--)
    {
        if (lst[col[i] ^ 1] != -1)
            minD[i] = min (minD[i], lst[col[i] ^ 1] - x[i]);
        lst[col[i]] = x[i];
    }
    for (int i=1; i<=N; i++)
        s[i] = s[i - 1] + x[i];
}

long long min_total_length (vector < int > rr, vector < int > bb)
{
    init (rr, bb);
    dp[0] = 0;
    int lst[2];
    lst[0] = lst[1] = -1;
    for (int i=1; i<=N; i++)
    {
        dp[i] = dp[i - 1] + minD[i];
        if (lst[col[i] ^ 1] != -1)
        {
            int k = lst[col[i] ^ 1];
            for (int j=k; j>=1; j--)
            {
                if (col[j] == col[i]) break;
                long long curr = dp[j - 1] + s[i] - s[k] - (s[k] - s[j - 1]);
                if (i - k > k - j + 1) curr -= 1LL * x[k] * ((i - k) - (k - j + 1));
                else curr += 1LL * x[k + 1] * ((k - j + 1) - (i - k));
                if (curr < dp[i])
                    dp[i] = curr;
            }
        }
        lst[col[i]] = i;
    }
	return dp[N];
}

Compilation message (stderr)

wiring.cpp: In function 'void init(std::vector<int>&, std::vector<int>&)':
wiring.cpp:13:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (pntr1 < rr.size () || pntr2 < bb.size ())
            ~~~~~~^~~~~~~~~~~~
wiring.cpp:13:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while (pntr1 < rr.size () || pntr2 < bb.size ())
                                  ~~~~~~^~~~~~~~~~~~
wiring.cpp:15:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (pntr2 == bb.size () || (pntr1 < rr.size () && rr[pntr1] < bb[pntr2]))
             ~~~~~~^~~~~~~~~~~~~
wiring.cpp:15:43: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (pntr2 == bb.size () || (pntr1 < rr.size () && rr[pntr1] < bb[pntr2]))
                                     ~~~~~~^~~~~~~~~~~~

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