Submission #341998

#	Time	Username	Problem	Language	Result	Execution time	Memory
341998		ijxjdjd	Wiring (IOI17_wiring)	C++14	100 / 100	90 ms	12124 KiB

wiring

using namespace std;
#include <bits/stdc++.h>
#include "wiring.h"
using ll = long long;
const ll INF = (ll)(1e18);
long long min_total_length(std::vector<int> r, std::vector<int> b) {
    int N = r.size();
    int M = b.size();
    vector<vector<int>> intervals;
    vector<int> cur;
    bool red = (r[0] < b[0]);
    int u = 0;
    int v = 0;
    r.push_back((int)(1e9)+5);
    b.push_back((int)(1e9) + 5);
    while (u < N || v < M) {
        if (r[u] < b[v]) {
            if (!red) {
                intervals.push_back(cur);
                cur.clear();
                red = true;
            }
            cur.push_back(r[u]);
            u++;
        }
        else {
            if (red) {
                intervals.push_back(cur);
                cur.clear();
                red = false;
            }
            cur.push_back(b[v]);
            v++;
        }
    }
    intervals.push_back(cur);
    vector<long long> dp(intervals[0].size()+1, 0LL);
    for (int i = 0; i < intervals[0].size(); i++) {
        dp[i] = INF;
    }
    for (ll e : intervals[0]) {
        dp[intervals[0].size()] -= e;
    }
    for (int i = 1; i < intervals.size(); i++) {
        vector<ll> next(intervals[i].size()+1, 0);
        multiset<ll> gr;
        multiset<ll> lseq;
        ll bef = *(intervals[i-1].end()-1);
        ll aft = intervals[i][0];
        ll addgr = -aft;
        ll addlseq = -bef;
        ll maintain = 0;
        for (int e = 0; e < dp.size(); e++) {
            gr.insert(dp[e] + e*aft);
        }
        for (int j = 0; j < intervals[i].size(); j++) {
            maintain -= intervals[i][j];
        }
        next[intervals[i].size()] = dp[0] + maintain;
        for (int k = 1; k <= intervals[i].size(); k++) {
            maintain += 2*intervals[i][k-1];
            if (k-1 < dp.size()) {
                gr.erase(gr.find(dp[k-1] - aft - addgr));
                lseq.insert(dp[k-1]-bef-addlseq);
            }
            next[intervals[i].size()-k] = maintain + min((gr.size() ? *gr.begin() : INF) + addgr, (*lseq.begin()) + addlseq);
            addgr -= aft;
            addlseq -= bef;
        }
        dp = next;
    }
    return dp[0];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:38:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for (int i = 0; i < intervals[0].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~~~~
wiring.cpp:44:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for (int i = 1; i < intervals.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~~~~
wiring.cpp:53:27: 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 e = 0; e < dp.size(); e++) {
      |                         ~~^~~~~~~~~~~
wiring.cpp:56:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |         for (int j = 0; j < intervals[i].size(); j++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~~
wiring.cpp:60:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |         for (int k = 1; k <= intervals[i].size(); k++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~~~
wiring.cpp:62:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |             if (k-1 < dp.size()) {
      |                 ~~~~^~~~~~~~~~~

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