Submission #171632

#TimeUsernameProblemLanguageResultExecution timeMemory
171632losmi247Wiring (IOI17_wiring)C++14
20 / 100
38 ms5372 KiB
#include <bits/stdc++.h> #include "wiring.h" using namespace std; typedef long long ll; const ll N = 1e5+34; const ll inf = 2e9; const ll linf = 1e18; ll dp[205][205]; ll najboljicrveni[205][205],najboljiplavi[205][205]; ll crveni[N],plavi[N]; int n,m; ll prvi(){ for(int i = 0; i <= n; i++){ for(int j = 0; j <= m; j++){ dp[i][j] = linf; najboljicrveni[i][j] = najboljiplavi[j][i] = linf; } } for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ najboljicrveni[i][j] = min(najboljicrveni[i][j-1],abs(crveni[i]-plavi[j])); } } for(int j = 1; j <= m; j++){ for(int i = 1; i <= n; i++){ najboljiplavi[j][i] = min(najboljiplavi[j][i-1],abs(plavi[j]-crveni[i])); } } dp[0][0] = 0; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ dp[i][j] = min({dp[i-1][j]+najboljicrveni[i][j],dp[i][j-1]+najboljiplavi[j][i],dp[i-1][j-1]+abs(crveni[i]-plavi[j])}); } } return dp[n][m]; } ll drugi(){ ll sol = 0,idc = n,idp = 1; while(idc >= 1 && idp <= m){ sol += plavi[idp]-crveni[idc]; idp++; idc--; } while(idc >= 1){ sol += plavi[1]-crveni[idc]; idc--; } while(idp <= m){ sol += plavi[idp]-crveni[n]; idp++; } return sol; } ll min_total_length(vector <int> r,vector <int> b){ n = r.size(),m = b.size(); ll maxr = 0,minb = inf; for(int i = 1; i <= n; i++){ crveni[i] = r[i-1]; maxr = max(maxr,crveni[i]); } for(int i = 1; i <= m; i++){ plavi[i] = b[i-1]; minb = min(minb,plavi[i]); } if(maxr < minb){ return drugi(); } if(n <= 200 && m <= 200){ return prvi(); } } /*int main(){ vector <int> a,b; cin >> n >> m; for(int i = 1; i <= n; i++){ int x; cin >> x; a.push_back(x); } for(int j = 1; j <= m; j++){ int x; cin >> x; b.push_back(x); } cout << min_total_length(a,b) << endl; }*/

Compilation message (stderr)

wiring.cpp: In function 'll min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:76:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^
#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...