제출 #427695

#제출 시각아이디문제언어결과실행 시간메모리
427695JeanBombeur전선 연결 (IOI17_wiring)C++17
7 / 100
57 ms10052 KiB
#include <iostream> #include <cstdio> #include <vector> #include <algorithm> #include "wiring.h" using namespace std; const long long INFINI = (1000 * 1000 * 1000); const int MAX_BLOCS = (200 * 1000); long long DP[MAX_BLOCS]; long long PrefixSum[MAX_BLOCS]; pair <long long, int> Positions[MAX_BLOCS]; int nbBlocs = 0; long long min_total_length(vector<int> Rouges, vector<int> Bleus) { Positions[nbBlocs ++] = {- INFINI, 0}; for (int a : Rouges) Positions[nbBlocs ++] = {(long long)a, 0}; for (int a : Bleus) Positions[nbBlocs ++] = {(long long)a, 1}; if (Positions[0].second != Positions[1].second) Positions[0].second ^= 1; sort(Positions, Positions + nbBlocs); for (int i = 1; i < nbBlocs; i ++) { PrefixSum[i] = PrefixSum[i - 1] + Positions[i].first; } int last = 1; for (int cur = 1; cur < nbBlocs; cur ++) { int next = cur; while (next < nbBlocs && Positions[cur].second == Positions[next].second) next ++; for (int i = last; i < cur; i ++) { DP[i] = min(DP[i], DP[i - 1] + Positions[cur].first - Positions[i].first); } long long coutTot = 0; long long mini = DP[cur - 1]; for (int i = cur; i < next; i ++) { long long nb = i - cur + 1; coutTot += Positions[i].first - Positions[cur - 1].first; int prev = cur - 1 - nb; if (prev + 1 >= last) { mini = min(mini, DP[prev] + nb * Positions[cur - 1].first - PrefixSum[cur - 1] + PrefixSum[prev]); } DP[i] = coutTot + mini; } last = cur; cur = next - 1; } return DP[nbBlocs - 1]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...