| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 637736 | dXqwq | 전선 연결 (IOI17_wiring) | C++17 | 0 ms | 0 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.
#ifndef local
#include "wiring.h"
#endif
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll min_total_length(vector<int> r,vector<int> b)
{
vector<vector<ll>> a,f,pre;
int n=r.size(),m=b.size(),i=0,j=0;
a.push_back({(ll)-1e18});
while(i<n&&j<m)
{
if(r[i]<b[j])
{
vector<ll> t;
while(i<n&&r[i]<b[j]) t.push_back(r[i++]);
a.push_back(t);
}
else
{
vector<ll> t;
while(j<m&&r[i]>b[j]) t.push_back(b[j++]);
a.push_back(t);
}
}
vector<ll> t;
while(i<n) t.push_back(r[i++]);
while(j<m) t.push_back(b[j++]);
a.push_back(t);
n=a.size(),a.push_back({(ll)1e18}),
f.resize(a.size()),pre.resize(a.size());
for(int i=0; i<=n; ++i)
{
f[i].resize(a[i].size()+1,(ll)1e18);
pre[i].resize(a[i].size());
int q=a[i].size();
pre[i][0]=a[i][0];
for(int j=1; j<q; ++j)
pre[i][j]=pre[i][j-1]+a[i][j];
}
f[1][0]=0;
for(int i=1; i<n; ++i)
{
int sz=a[i].size(),ts=a[i+1].size();
ll sum=0;
f[i][0]=min(f[i][0],f[i][1]),
f[i+1][0]=f[i][sz];
for(int j=sz-1; j>=0; --j)
sum-=a[i][j],f[i][j]+=sum;
//j<=k
ll tmp=1e18;
for(int k=1; k<=ts; ++k)
{
tmp-=a[i].back();
if(k<=sz) tmp=min(tmp,f[i][sz-k]);
f[i+1][k]=min(f[i+1][k],tmp);
}
tmp=1e18;
for(int k=sz; k>ts; --k)
{
tmp+=a[i+1][0];
if(k<=sz) tmp=min(tmp,f[i][sz-k]);
}
for(int k=ts; k>=1; --k)
{
tmp+=a[i+1][0];
if(k<=sz) tmp=min(tmp,f[i][sz-k]);
f[i+1][k]=min(f[i+1][k],tmp);
}
for(int j=1; j<=ts; ++j)
f[i+1][j]+=pre[i+1][j-1];
}
return f[n][0];
}
#ifdef local
#include <cassert>
#include <cstdio>
using namespace std;
int main() {
int n, m;
assert(2 == scanf("%d %d", &n, &m));
vector<int> r(n), b(m);
for(int i = 0; i < n; i++)
assert(1 == scanf("%d", &r[i]));
for(int i = 0; i < m; i++)
assert(1 == scanf("%d", &b[i]));
long long res = min_total_length(r, b);
printf("%lld\n", res);
return 0;
}
#endif