제출 #1060291

#제출 시각아이디문제언어결과실행 시간메모리
1060291TahirAliyevWiring (IOI17_wiring)C++17
0 / 100
1 ms348 KiB
#include "wiring.h" #include <bits/stdc++.h> using namespace std; #define pii pair<int, int> #define oo 1e9 long long min_total_length(std::vector<int> r, std::vector<int> b) { #define int long long int n = r.size() + b.size(); vector<pii> v = {{0, 0}}; for(int a : r) v.push_back({a, 0}); for(int a : b) v.push_back({a, 1}); sort(v.begin() + 1, v.end()); vector<int> pre(n + 1, 0), prex(n + 1, 0), dp(n + 1, 0), clo(2, -oo); map<int, int> mp = {{0, 0}}; for(int i = 1; i <= n; i++){ pre[i] = pre[i - 1] + ((v[i].second)? -1 : 1); prex[i] = prex[i - 1] + ((v[i].second)? -1 : 1) * v[i].first; dp[i] = dp[i - 1] + v[i].first - clo[v[i].second ^ 1]; clo[v[i].second] = v[i].first; if(mp.count(pre[i])){ int id = mp[pre[i]]; dp[i] = min(dp[id] + abs(prex[i] - prex[id]), dp[i]); } mp[pre[i]] = i; } #undef int return n; }
#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...