# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
286446 | peti1234 | Wiring (IOI17_wiring) | C++17 | 78 ms | 6648 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
const int c=200002;
long long n, kom[c], dp[c], el=1, veg, o=0;
pair<int, int> a[c];
long long min_total_length(std::vector<int> r, std::vector<int> b) {
for (int i=0; i<r.size(); i++) a[++n]={r[i], 0};
for (int i=0; i<b.size(); i++) a[++n]={b[i], 1};
sort(a+1, a+n+1);
for (int i=1; i<=n; i++) kom[i]=kom[i-1]+a[i].first;
a[0]={-1e9, 0};
for (int i=1; i<=n; i++) {
while(veg<n && a[veg+1].second==a[i].second) veg++;
for (int k=el; k<i; k++) dp[k]=min(dp[k], dp[k-1]+a[i].first-a[k].first);
long long s=dp[i-1], v=0;
for (int k=i; k<=veg; k++) {
v+=a[k].first-a[i-1].first;
long long db=k-i+1;
if (db<=i-el) s=min(s, dp[max(o, i-db-1)]+db*a[i-1].first-kom[i-1]+kom[max(o, i-db-1)]);
dp[k]=s+v;
}
el=i, i=veg;
}
return dp[n];
}
Compilation message (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... |