Submission #1247058

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247058		nvc2k8	Wiring (IOI17_wiring)	C++20	100 / 100	20 ms	9032 KiB

wiring

#include <bits/stdc++.h>
#include "wiring.h"
#define TASK "wiring"
#define endl '\n'
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define BIT(i,x) (((i)>>(x))&1)
#define FOR(i,a,b) for(int i = (a); i<=(b); i++)
#define FORD(i,a,b) for(int i = (a); i>=(b); i--)
#define all(C) C.begin(), C.end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int INT_LIM = 2147483647;
const ll LL_LIM = 9223372036854775807;
template <typename X> bool minimize(X &x, const X &y) {if (x>y){x = y; return true;}return false;}
template <typename X> bool maximize(X &x, const X &y) {if (x<y){x = y; return true;}return false;}
///------------------------------------------///
int n,m;
int a[100005], b[100005], c[200005], color[200005];
ll pf[200005];
ll dp[200005];
ll minpf[200005], minsf[200005];

ll get(int l, int r)
{
    return pf[r]-pf[l-1];
}

ll min_total_length(vector<int> R, vector<int> B) {
    n = R.size(); m = B.size();
    FOR(i, 1, n) a[i] = R[i-1];
    FOR(i, 1, m) b[i] = B[i-1];
    for (int i = 1, j = 1; i<=n || j<=m;)
    {
        if (i>n)
        {
            c[i+j-1] = b[j];
            color[i+j-1] = 1;
            j++;
        }
        else if (j>m)
        {
            c[i+j-1] = a[i];
            color[i+j-1] = 0;
            i++;
        }
        else
        {
            if (a[i]<b[j])
            {
                c[i+j-1] = a[i];
                color[i+j-1] = 0;
                i++;
            }
            else
            {
                c[i+j-1] = b[j];
                color[i+j-1] = 1;
                j++;
            }
        }
    }

    FOR(i, 1, n+m)
    {
        dp[i] = LL_LIM;
        pf[i] = pf[i-1]+c[i];
    }

    int prsz = 0;
    for (int R = n+m; R>=1; )
    {
        int L = 1;
        FORD(i, R, 1)
        {
            if (color[i]!=color[R]) break;
            L = i;
        }

        if (R<n+m)
        {
            FOR(i, L, R)
            {
                if (prsz==1)
                {
                    if (dp[R+2]!=LL_LIM) minimize(dp[i], 1LL*c[R+1]*(R-i+1) - get(i, R) + dp[R+2]);
                    if (dp[R+1]!=LL_LIM) minimize(dp[i], 1LL*c[R+1]*(R-i+1) - get(i, R) + dp[R+1]);
                    continue;
                }
                int t = min(R-i+1, prsz);
                if (minpf[t]!=LL_LIM) minimize(dp[i], 1LL*c[R+1]*(R-i+1) - get(i,R) + minpf[t]);

                if (R-i+1<prsz)
                if (minsf[R-i+2]!=LL_LIM) minimize(dp[i], 1LL*c[R]*(R-i+1) - get(i, R) + minsf[R-i+2]);
            }
        }

        if (L>1)
        {
            minpf[0] = LL_LIM;
            FOR(i, L, R)
            {
                minpf[i-L+1] = LL_LIM;
                if (dp[i+1]!=LL_LIM) minimize(minpf[i-L+1], get(L,i) - 1LL*c[L]*(i-L+1) + dp[i+1]);
                minimize(minpf[i-L+1], minpf[i-L]);
            }
            minsf[R-L+2] = LL_LIM;
            FORD(i, R, L)
            {
                minsf[i-L+1] = LL_LIM;
                if (dp[i+1]!=LL_LIM) minimize(minsf[i-L+1], get(L,i) - 1LL*c[L-1]*(i-L+1) + dp[i+1]);
                minimize(minsf[i-L+1], minsf[i-L+2]);
            }
        }

        if (L==1) break;
        prsz = R-L+1;
        R = L-1;
    }


	return dp[1];
}

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