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;
#define endl '\n'
#define st first
#define nd second
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define ll long long
ll mod=1000000007;
int inf=1000000007;
ll infl=1000000000000000007;
const int N=200007;
ll DP[N][(1<<7)+7];
ll min_total_length(vector<int>r,vector<int>b)
{
vector<pair<ll,int>>V,V1;
int n=sz(r),m=sz(b);
for(int i=0;i<n;i++) V.pb({r[i],0});
for(int i=0;i<m;i++) V.pb({b[i],1});
sort(all(V));
set<int>S[2];
S[0].insert(-inf),S[0].insert(inf),S[1].insert(-inf),S[1].insert(inf);
for(int i=0;i<n+m;i++) S[V[i].nd].insert(i);
ll sum=0;
for(int i=0;i<n+m;i++)
{
int l=*--S[V[i].nd^1].upper_bound(i);
int r=*S[V[i].nd^1].upper_bound(i);
if(i-l<=3||r-i<=3) V1.pb(V[i]);
else
{
ll mn=infl;
if(l!=-inf) mn=V[i].st-V[l].st;
if(r!=inf) mn=min(mn,V[r].st-V[i].st);
sum+=mn;
}
}
for(int i=0;i<sz(V1);i++)
{
for(int j=0;j<(1<<7);j++) DP[i+1][j]=infl;
for(int j=1;j<(1<<7);j+=2) DP[i+1][j/2]=DP[i][j];
for(int j=0;j<(1<<7);j++)
{
for(int l=0;l<6;l++)
{
if(i-6+l>=0&&V1[i].nd!=V1[i-6+l].nd)
{
DP[i+1][j|(1<<l)|(1<<6)]=min(DP[i+1][j|(1<<l)|(1<<6)],DP[i+1][j]+V1[i].st-V1[i-6+l].st);
}
}
}
}
return sum+DP[sz(V1)][(1<<7)-1];
}
/*
int main()
{
cout<<min_total_length({1, 2, 3, 7},{0, 4, 5, 9, 10})<<endl;
return 0;
}
*/
# | 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... |