# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
482498 | couplefire | 전선 연결 (IOI17_wiring) | C++17 | 54 ms | 10388 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll ckmin(ll &a, ll b){return a<b?a:a=b;}
ll min_total_length(vector<int> a, vector<int> b){
int n = a.size(), m = b.size();
vector<vector<int>> groups;
vector<array<int, 2>> arr;
for(auto x : a) arr.push_back({x, 0});
for(auto x : b) arr.push_back({x, 1});
sort(arr.begin(), arr.end());
for(int i = 0; i<n+m; ++i){
groups.push_back({arr[i][0]});
while(i<n+m-1 && arr[i][1]==arr[i+1][1]) ++i, groups.back().push_back(arr[i][0]);
}
vector<ll> dp(n+m, 1e18);
for(int i = 0, cnt = 0; i<groups.size(); cnt += groups[i].size(), ++i){
ll s1 = 0, s2 = 0;
for(int j = 0; j<groups[i].size(); ++j){
ll prv = (cnt==0 && j==0)?0ll:dp[cnt+j-1];
s2 += groups[i][j]; if(cnt && (int)groups[i-1].size()>j) s1 += groups[i-1][(int)groups[i-1].size()-1-j];
if(cnt) ckmin(dp[cnt+j], prv+groups[i][j]-groups[i-1].back());
if(cnt+groups[i].size()<n+m) ckmin(dp[cnt+j], prv+groups[i+1].front()-groups[i][j]);
ll bruh = (!cnt || (int)groups[i-1].size()<=j || (i==1 && (int)groups[i-1].size()==j+1))?0ll:dp[cnt-j-2];
if(cnt && (int)groups[i-1].size()>j) ckmin(dp[cnt+j], bruh+s2-s1);
}
}
return dp[n+m-1];
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |