Submission #280328

#	Time	Username	Problem	Language	Result	Execution time	Memory
280328		Noam13	Wiring (IOI17_wiring)	C++14	100 / 100	65 ms	9356 KiB

wiring

#include <bits/stdc++.h>
#define int int64_t
#define vi vector<int>
#define vvi vector<vi>
#define vb vector<bool>
#define vvb vector<vb>
#define ii pair<int, int>
#define x first
#define y second
#define vii vector<ii>
#define pb push_back
#define all(x) x.begin(), x.end()
#define loop(i,s,e) for(int i=s;i<e;++i)
#define chkmin(a,b) a = min(a,b)
#define chkmax(a,b) a = max(a,b)
using namespace std;
const int INF = 2e18;


int min_total_length(vector<int32_t> r, vector<int32_t> b){
    vi cur, last;
    vi vals, lvals(1,0), v1, v2;
    int i = 0, j = 0, n = r.size(), m = b.size();
    auto get = [&](){
        int who = 0;
        if (i==n || (j!=m && r[i]>b[j])) who = 1;
        if (i==n && j==m) who = -1;
        return who;
    };
    int lastp = 0;
    while(1){
        int who = get();
        if (who==-1) break;
        int nextp = 0;
        while(1){
            if (who) cur.pb(b[j++]);
            else cur.pb(r[i++]);
            if (who!=get()) {
                if (who && i<n) nextp = r[i];
                if (!who && j<m) nextp = b[j];
                break;
            }
        }
        int mm = last.size(), nn = cur.size();
        vals.resize(nn+1, INF); vals[0] = lvals[0];
        //cout<<"HI: "<<i<<" "<<j<<endl;
        if (mm){
            int prefa = 0, prefb = 0;
            loop(k,0,nn){
                prefa+=cur[k]-lastp; prefb+=cur[k]-cur[0];
                chkmin(vals[k+1], prefa + v1[min(k, mm-1)]);
                if (k<mm) chkmin(vals[k+1], prefb + v2[k]);
            } 
        }
        reverse(all(cur)); reverse(all(vals));
        loop(i,0,nn) chkmin(vals[i+1], vals[i]);
        lastp = cur[0];
        loop(k,1,nn) cur[k]+=cur[k-1];
        v2 = v1 = cur;
        loop(k,0,nn) v1[k]=(k+1)*lastp -cur[k] + vals[k+1];
        loop(k,0,nn) v2[k]= (k+1)*nextp -cur[k] + vals[k+1];
        loop(k,1,nn) chkmin(v1[k], v1[k-1]);
        loop(k,1,nn) chkmin(v2[nn-k-1], v2[nn-k]);
        last = cur; cur.clear();
        lvals = vals; vals.clear();
    }
    return lvals[0];
}

/*
clear
g++ b.cpp grader.cpp -o c ; ./c
4 5
1 2 3 7
0 4 5 9 10
*/

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