Submission #244633

#	Time	Username	Problem	Language	Result	Execution time	Memory
244633		LittleFlowers__	Wiring (IOI17_wiring)	C++17	30 / 100	85 ms	6760 KiB

wiring

#include <bits/stdc++.h>
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r){return l+rng()%(r-l+1);}
#define fasty ios_base::sync_with_stdio(0),cin.tie(0);
#define forinc(a,b,c) for(int a=b,_c=c;a<=_c;++a)
#define fordec(a,b,c) for(int a=b,_c=c;a>=_c;--a)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f, x) memset(f, x, sizeof(f))
#define gg exit(0);

long long min_total_length(vector<int> r, vector<int> b){
    int m=r.size(), n=b.size();


    if(m<=200 && n<=200){
        vector<vector<long long>> f(m+5,vector<long long>(n+5,1e15));
        f[0][0]=0;
        forinc(i,0,m) forinc(j,0,n){
            if(j) f[i+1][j]=min(f[i+1][j],f[i][j]+abs(r[i]-b[j-1]));
            if(i) f[i][j+1]=min(f[i][j+1],f[i][j]+abs(r[i-1]-b[j]));
            f[i+1][j+1]=min(f[i+1][j+1],f[i][j]+abs(r[i]-b[j]));
        }
        return f[m][n];
    }

    if(r[m-1]<b[0]){
        long long i=m-1, j=0, tot=0;
        while(i>=0 && j<n) tot+=abs(r[i--]-b[j++]);
        while(i>=0) tot+=abs(r[i--]-b[0]);
        while(j<n)  tot+=abs(r[m-1]-b[j++]);
        return tot;
    }


    vector<pair<long long,long long>> a;
    forv(i,r) a.pb({i,1});
    forv(i,b) a.pb({i,0});
    sort(all(a));

    int cr=0, cb=0, task3=1;
    forinc(i,1,m+n){
        (a[i-1].se ? cb++ : cr++);
        if(i>7) (a[i-8].se ? cb-- : cr--);
        if(i>=7) task3&=cb && cr;
    }
    if(task3){
        vector<long long> s(m+n+1);
        forinc(i,1,m+n) s[i]=s[i-1]+a[i-1].fi;
        int i=0, cnt=0, sz=0;
        vector<long long> f(100,1e15);
        f[0]=0;
        while(i<m+n){
            vector<long long> g(100,1e15);
            cnt++;
            int j=i;
            while(j<m+n && a[j].se==a[i].se) j++;

            g[j-i]=min(g[j-i],f[0]);
            forinc(t,0,sz){
                forinc(k,1,j-i){
                    if(!t && !i) continue;
                    g[j-i-k]=min(g[j-i-k],f[t]+(s[i+k]-s[i]) - (s[i]-s[i-t]) + a[i-(t<k)].fi*(t-k));
                }
            }
            swap(f,g);
            sz=j-i;
            i=j;
        }
        return f[0];
    }


    if(max(r[m-1],b[n-1])<=m+n){

    }
}

//#define unx

#ifdef unx
main(){
    #define task "TASK"
    if(fopen(task".inp","r")){
        freopen(task".inp","r",stdin);
        //freopen(task".out","w",stdout);
    }

    vector<vector<int>> a;
    forinc(i,0,1){
        a.emplace_back();
        int n; cin>>n; a.back().resize(n);
        forv(j,a.back()) cin>>j;
    }
    cout<<min_total_length(a[0],a[1]);
}
#endif // unx

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:84:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• Subtask 1: 7 / 7
• Subtask 2: 13 / 13
• Subtask 3: 10 / 10
• Subtask 4: 0 / 25
• Subtask 5: 0 / 45