Submission #482497

#	Time	Username	Problem	Language	Result	Execution time	Memory
482497		couplefire	Wiring (IOI17_wiring)	C++17	0 / 100	64 ms	8248 KiB

wiring

#include <bits/stdc++.h>
using namespace std;
#define ll long long

ll ckmin(ll &a, ll b){return a<b?a:a=b;}

ll min_total_length(vector<int> a, vector<int> b){
    int n = a.size(), m = b.size();
    vector<vector<int>> groups;
    vector<array<int, 2>> arr;
    for(auto x : a) arr.push_back({x, 0});
    for(auto x : b) arr.push_back({x, 1});
    sort(arr.begin(), arr.end());
    for(int i = 0; i<n+m; ++i){
        groups.push_back({arr[i][0]});
        while(i<n+m-1 && arr[i][1]==arr[i+1][1]) ++i, groups.back().push_back(arr[i][0]);
    }
    vector<ll> dp(n+m, 1e18);
    for(int i = 0, cnt = 0; i<groups.size(); cnt += groups[i].size(), ++i){
        ll s1 = 0, s2 = 0;
        for(int j = 0; j<groups[i].size(); ++j){
            ll prv = (cnt==0 && j==0)?0ll:dp[cnt+j-1];
            s2 += groups[i][j]; if(cnt && (int)groups[i-1].size()>j) s1 += groups[i-1][(int)groups[i-1].size()-1-j];
            if(cnt) ckmin(dp[cnt+j], prv+groups[i][j]-groups[i-1].back());
            if(cnt+groups[i].size()<n+m) ckmin(dp[cnt+j], prv+groups[i+1].front()-groups[i][j]);
            ll bruh = (!cnt || (int)groups[i-1].size()<=j || (cnt==1 && (int)groups[i-1].size()==j+1))?0:dp[cnt-j-2];
            if(cnt && (int)groups[i-1].size()>j) ckmin(dp[cnt+j], bruh+s2-s1);
        }
    }
    return dp[n+m-1];
}

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:19:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for(int i = 0, cnt = 0; i<groups.size(); cnt += groups[i].size(), ++i){
      |                             ~^~~~~~~~~~~~~~
wiring.cpp:21:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         for(int j = 0; j<groups[i].size(); ++j){
      |                        ~^~~~~~~~~~~~~~~~~
wiring.cpp:25:36: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   25 |             if(cnt+groups[i].size()<n+m) ckmin(dp[cnt+j], prv+groups[i+1].front()-groups[i][j]);
      |                ~~~~~~~~~~~~~~~~~~~~^~~~

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