Submission #434526

#	Time	Username	Problem	Language	Result	Execution time	Memory
434526		Everule	Wiring (IOI17_wiring)	C++17	55 / 100	57 ms	9644 KiB

wiring

#include <bits/stdc++.h>
using namespace std;
using ll = long long int;
#include "wiring.h"
const ll INF = 1e18;
long long min_total_length(std::vector<int> a, std::vector<int> b) {
    int n = a.size();
    int m = b.size();
    vector<vector<int>> ord;
    for(int i=0,j=0;i<n;i++){
        if(j < m && b[j] < a[i]){
            ord.push_back({});
            while(j < m && b[j] < a[i]){
                ord.back().push_back(b[j]);
                j++;
            }
            ord.push_back({});
        }
        if(ord.size() == 0) ord.push_back({});
        ord.back().push_back(a[i]);
        if(i == n - 1){
            if(j < m){
                ord.push_back({});
                while(j < m){
                    ord.back().push_back(b[j]);
                    j++;
                }
            }
        }
    }
    int r = ord.size();
    /*
    cout<<r<<"\n";
    for(auto &v : ord){
        for(auto &x : v){
            cout<<x<<" ";
        }
        cout<<"\n";
    }
    */
    vector<vector<ll>> dp(r);
    for(int i=0;i<r;i++){
        dp[i].assign(ord[i].size() + 1, INF);
    }
    [&](){
        int wl = ord[0].size();
        ll ans = 0;
        for(auto &x : ord[0]) ans -= x;
        dp[1][0] = INF;
        dp[1][1] = ans + ll(wl) * ord[1][0];
        for(int i=1;i<ord[1].size();i++){
            if(i < wl) dp[1][i+1] = dp[1][i] + (ord[1][i] - ord[1][0]);
            else dp[1][i+1] = dp[1][i] + (ord[1][i] - ord[0].back());
        }
    }();
    for(int i=2;i<r;i++){
        dp[i][0] = dp[i-1].back();
        for(ll j=dp[i-1].size()-1,sum = 0;j>=0;j--){
            dp[i-1][j] += sum;
            if(j != 0) sum += ord[i][0] - ord[i-1][j-1];
        }
        for(int j=1;j<dp[i-1].size();j++){
            dp[i-1][j] = min(dp[i-1][j-1], dp[i-1][j]);
        }
        ll bst = *min_element(dp[i-1].begin(), dp[i-1].end());
        ll def = 0;
        for(int j=0;j<ord[i].size();j++){
            def += ord[i][j] - ord[i-1].back();
            if(j+2 <= dp[i-1].size()){
                dp[i-1].end()[-(j+2)] -= (j + 1) * (ord[i][0] - ord[i-1].back());
                bst = min(bst, dp[i-1].end()[-(j+2)]);
            }
          
            dp[i][j+1] = bst + def;
        }        
    }
    /*
    for(auto &v : dp){
        for(auto &x : v){
            cout<<x<<" ";
        }
        cout<<"\n";
    }
    */
    return dp.back().back();
}

Compilation message (stderr)

wiring.cpp: In lambda function:
wiring.cpp:51:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |         for(int i=1;i<ord[1].size();i++){
      |                     ~^~~~~~~~~~~~~~
wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:62:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         for(int j=1;j<dp[i-1].size();j++){
      |                     ~^~~~~~~~~~~~~~~
wiring.cpp:67:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         for(int j=0;j<ord[i].size();j++){
      |                     ~^~~~~~~~~~~~~~
wiring.cpp:69:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |             if(j+2 <= dp[i-1].size()){
      |                ~~~~^~~~~~~~~~~~~~~~~

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