# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1042418 | Math4Life2020 | Palembang Bridges (APIO15_bridge) | C++17 | 2065 ms | 10328 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
ll calc(vector<ll> v) {
vector<ll> v2=v;
sort(v2.begin(),v2.end());
ll val = 0;
for (ll x: v2) {
val += abs(x-v2[v2.size()/2]);
}
return val;
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
ll K,N; cin >> K >> N;
vector<pii> v;
ll ans = 0;
for (ll i=0;i<N;i++) {
string p,q; ll s,t;
cin >> p >> s >> q >> t;
if (p==q) {
ans += abs(s-t);
} else {
ans++;
v.push_back({min(s,t),max(s,t)});
}
}
vector<ll> v2;
for (pii p0: v) {
v2.push_back(p0.first);
v2.push_back(p0.second);
}
sort(v2.begin(),v2.end());
if (K==1) {
cout << ans+calc(v2);
} else {
ll ans1[v.size()+1]; ll ans2[v.size()+1];
vector<array<ll,3>> VTOT;
for (ll i=0;i<v.size();i++) {
VTOT.push_back({v[i].first+v[i].second,v[i].first,v[i].second});
}
sort(VTOT.begin(),VTOT.end());
ans1[0]=0; ans2[v.size()]=0;
vector<ll> vf; vector<ll> vb;
for (ll T=0;T<VTOT.size();T++) {
vf.push_back(VTOT[T][1]);
vf.push_back(VTOT[T][2]);
ans1[T+1]=calc(vf);
vb.push_back(VTOT[v.size()-1-T][1]);
vb.push_back(VTOT[v.size()-1-T][2]);
ans2[v.size()-1-T]=calc(vb);
}
ll atotM = 1e18;
for (ll i=0;i<=v.size();i++) {
atotM = min(atotM,ans1[i]+ans2[i]);
}
cout << ans+atotM;
}
}
컴파일 시 표준 에러 (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... |