Submission #286446

#	Time	Username	Problem	Language	Result	Execution time	Memory
286446		peti1234	Wiring (IOI17_wiring)	C++17	100 / 100	78 ms	6648 KiB

wiring

#include<bits/stdc++.h>
using namespace std;
const int c=200002;
long long n, kom[c], dp[c], el=1, veg, o=0;
pair<int, int> a[c];
long long min_total_length(std::vector<int> r, std::vector<int> b) {
    for (int i=0; i<r.size(); i++) a[++n]={r[i], 0};
    for (int i=0; i<b.size(); i++) a[++n]={b[i], 1};
    sort(a+1, a+n+1);
    for (int i=1; i<=n; i++) kom[i]=kom[i-1]+a[i].first;
    a[0]={-1e9, 0};
    for (int i=1; i<=n; i++) {
        while(veg<n && a[veg+1].second==a[i].second) veg++;
        for (int k=el; k<i; k++) dp[k]=min(dp[k], dp[k-1]+a[i].first-a[k].first);
        long long s=dp[i-1], v=0;
        for (int k=i; k<=veg; k++) {
            v+=a[k].first-a[i-1].first;
            long long db=k-i+1;
            if (db<=i-el) s=min(s, dp[max(o, i-db-1)]+db*a[i-1].first-kom[i-1]+kom[max(o, i-db-1)]);
            dp[k]=s+v;
        }
        el=i, i=veg;
    }
    return dp[n];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:7:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    7 |     for (int i=0; i<r.size(); i++) a[++n]={r[i], 0};
      |                   ~^~~~~~~~~
wiring.cpp:8:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    8 |     for (int i=0; i<b.size(); i++) a[++n]={b[i], 1};
      |                   ~^~~~~~~~~

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