Submission #171180

#	Time	Username	Problem	Language	Result	Execution time	Memory
171180		alexandra_udristoiu	Wiring (IOI17_wiring)	C++14	13 / 100	43 ms	8696 KiB

wiring

#include<iostream>
#include<vector>
#include "wiring.h"
#define DIM 200005
#define f first
#define s second
using namespace std;
static long long d[DIM], sp[DIM];
pair<int, int> v[DIM];
long long min_total_length(vector<int> r, vector<int> b) {
    int n, m, i, j, curr, prv, ind;
    long long sum1, sum2, minim;
    n = r.size();
    m = b.size();
    i = j = 0;
    while(i < n && j < m){
        if(r[i] < b[j]){
            v[i + j + 1] = make_pair(r[i], 0);
            i++;
        }
        else{
            v[i + j + 1] = make_pair(b[j], 1);
            j++;
        }
    }
    for(; i < n; i++){
        v[i + j + 1] = make_pair(r[i], 0);
    }
    for(; j < m; j++){
        v[i + j + 1] = make_pair(b[j], 1);
    }
    n += m;
    for(i = 1; i <= n; i++){
        sp[i] = sp[i - 1] + v[i].f;
    }
    prv = 1;
    sum1 = v[1].f;
    sum2 = 0;
    for(i = 2; i <= n; i++){
        if(v[i].s != v[i - 1].s){
            curr = i;
            break;
        }
        else{
            sum1 += v[i].f;
        }
    }
    for(; i <= n; i++){
        sum2 += v[i].f;
        d[i] = sum2 - sum1;
        if(i - curr + 1 < curr - prv){
            d[i] += ( (curr - prv) - (i - curr + 1) ) * 1LL * v[curr].f;
        }
        else{
            d[i] -= ( (i - curr + 1) - (curr - prv) ) * 1LL * v[curr - 1].f;
        }
        if(v[i + 1].s != v[i].s){
            break;
        }
    }
    for(i = i + 1; i <= n; i++){
        if(v[i - 1].s != v[i].s){
            prv = curr;
            curr = i;
            minim = min(d[i - 1], d[i - 2]) + v[i].f - v[i - 1].f;
            d[i] = minim;
            ind = i - 1;
        }
        else{
            minim += v[i].f - v[curr - 1].f;
            if(i - curr + 1 <= curr - prv){
                ind--;
            }
            minim = min(minim, d[ind - 1] + sp[i] - sp[curr - 1] - sp[curr - 1] + sp[ind - 1]);
            d[i] = minim;
        }
    }
    return d[n];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:70:19: warning: 'minim' may be used uninitialized in this function [-Wmaybe-uninitialized]
             minim += v[i].f - v[curr - 1].f;
                   ^
wiring.cpp:11:32: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int n, m, i, j, curr, prv, ind;
                                ^~~
wiring.cpp:71:37: warning: 'curr' may be used uninitialized in this function [-Wmaybe-uninitialized]
             if(i - curr + 1 <= curr - prv){
                                ~~~~~^~~~~

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