Submission #482496

#TimeUsernameProblemLanguageResultExecution timeMemory
482496couplefireWiring (IOI17_wiring)C++17
0 / 100
45 ms13176 KiB
#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((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]);
      |                ~~~~~~~~~~~~~~~~~~~~^~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...