Submission #579812

#	Time	Username	Problem	Language	Result	Execution time	Memory
579812		definitelynotmee	Wiring (IOI17_wiring)	C++98	100 / 100	67 ms	8288 KiB

wiring

#include<bits/stdc++.h>
#include"wiring.h"
#define ff first
#define ss second
#define all(x) x.begin(), x.end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;
const ll INFL = 5e17;

struct smartset{
    ll lz = 0;
    multiset<ll> s = {INFL};
    void insert(ll i){
        s.insert(i-lz);
    }
    void add(ll x){
        lz+=x;
    }
    ll min(){
        return *s.begin()+lz;
    }
    void remove(ll x){
        s.erase(s.find(x));
    }
};

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

    int p1 = 0, p2 = 0;
    vector<ll> lastdp ={0};
    ll lastx = -1;

    while(p1 < n && p2 < m){
        if(r[p1] > b[p2]){
            swap(r,b);
            swap(p1,p2);
            swap(n,m);
        }
        vector<ll> cur;
        while(p1 < n && r[p1] < b[p2]){
            cur.push_back(r[p1]);
            p1++;
        }
        vector<ll> dp(cur.size()+1,INFL);
        ll discount = cur[0]-lastx;
        if(lastx == -1){
            dp[0] = 0;
            for(int i = 0; i < cur.size(); i++){
                dp[0]+=b[p2]-cur[i];
            }
        } else [[likely]] {
            
            smartset s;
            int sz = lastdp.size();
            ll mindp = INFL;
            ll connect = 0;
            for(ll i : lastdp)
                s.insert(i);

            for(int i = 0; i < cur.size(); i++){
                connect+=b[p2]-cur[i];
            }
            for(int i = 0; i < cur.size(); i++){
                mindp = min(mindp,s.min());
                dp[i] = connect + mindp;

                if(sz-i-1 >= 0)
                    s.remove(lastdp[sz-i-1]);

                connect-=b[p2]-cur[i];
                connect+=cur[i]-lastx;
                s.add(-discount);
            }
            mindp = min(mindp,s.min());
            dp.back() = connect+mindp;

        }
        lastx = cur.back();
        swap(dp,lastdp);
    }
    int ct = 0;
    ll discount = b[p2]-lastx;
    ll cost = 0, resp = INFL;
    while(p2 < m){
        cost+=b[p2]-lastx;
        ct++;
        p2++;
    }
    int sz = lastdp.size();
    for(int i = 0; i < sz; i++){
        resp = min(resp, cost+lastdp[i]-min(ct,sz-i-1)*discount);
    }
    return resp;
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:53:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   53 |             for(int i = 0; i < cur.size(); i++){
      |                            ~~^~~~~~~~~~~~
wiring.cpp:65:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |             for(int i = 0; i < cur.size(); i++){
      |                            ~~^~~~~~~~~~~~
wiring.cpp:68:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |             for(int i = 0; i < cur.size(); i++){
      |                            ~~^~~~~~~~~~~~

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