Submission #244226

#	Time	Username	Problem	Language	Result	Execution time	Memory
244226		LittleFlowers__	Wiring (IOI17_wiring)	C++17	20 / 100	42 ms	3832 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];
    }

    sort(all(r)); sort(all(b));

    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;
    }
}

//#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:41:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

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