Submission #586853

#	Time	Username	Problem	Language	Result	Execution time	Memory
586853		MohamedFaresNebili	전선 연결 (IOI17_wiring)	C++14	100 / 100	52 ms	15260 KiB

wiring

#include <bits/stdc++.h>
/// #pragma GCC optimize ("Ofast")
/// #pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")

                        using namespace std;

                        using ll = long long;
                        using ii = pair<ll, ll>;
                        using vi = vector<int>;

                        #define ff first
                        #define ss second
                        #define pb push_back
                        #define all(x) (x).begin(), (x).end()
                        #define lb lower_bound

                        const int MOD = 1000 * 1000 * 1000 + 7;

                        ll DP[222222], D[222222], P[222222], M[444444];
                        ll min_total_length(vector<int> R, vector<int> B) {
                            int N = R.size() + B.size(); vector<pair<ll, ll>> A;
                            for(auto u : R) A.push_back({u, -1});
                            for(auto u : B) A.push_back({u, 1});

                            sort(A.begin(), A.end()); memset(M, -1, sizeof M);
                            ll U = -1, V = -1;

                            for(int l = 1; l <= N; l++)
                                P[l] = P[l - 1] + A[l - 1].ff * A[l - 1].ss;

                            for(int l = 0; l < N; l++) {
                                D[l] = 1e18 + 7;
                                if(A[l].ss == -1) {
                                    if(V != -1) D[l] = min(D[l], A[l].ff - V);
                                    U = A[l].ff; continue;
                                }
                                if(U != -1) D[l] = min(D[l], A[l].ff - U);
                                V = A[l].ff; continue;
                            }
                            U = -1, V = -1; ll curr = N;
                            for(int l = N - 1; l >= 0; l--) {
                                if(A[l].ss == -1) {
                                    if(V != -1) D[l] = min(D[l], V - A[l].ff);
                                    U = A[l].ff; continue;
                                }
                                if(U != -1) D[l] = min(D[l], U - A[l].ff);
                                V = A[l].ff; continue;
                            }

                            M[N] = 0;
                            for(int l = 1; l <= N; l++) {
                                curr += A[l - 1].ss;
                                DP[l] = D[l - 1] + DP[l - 1];
                                if(M[curr] != -1)
                                    DP[l] = min(DP[l], DP[M[curr]] + abs(P[l] - P[M[curr]]));
                                M[curr] = l;
                            }

                            return DP[N];
                        }

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