Submission #578019

#TimeUsernameProblemLanguageResultExecution timeMemory
578019AugustinasJucasWiring (IOI17_wiring)C++14
17 / 100
1092 ms16128 KiB
#include <bits/stdc++.h> using namespace std; #include "wiring.h" int n; const long long inf = 1e18; vector<int> groupInd; vector<pair<int, int> > interv; vector<pair<int, int> > groups; vector<long long> toRight, toLeft; vector<long long> ikiL, ikiR; vector<long long> kaimL, kaimR; long long f(int l, int r) { long long ret = 0; ret += toRight[l]; ret += toLeft[r]; ret += kaimR[l] * max(ikiR[l], ikiL[r]); return ret; } void calcToLeft(int l, int r, int ind) { int dst = -1; if(ind != 0) dst = abs(groups[interv[ind-1].second].first - groups[l].first); for(int i = l; i <= r; i++) { toLeft[i] = (i == l ? 0ll : toLeft[i-1]) + groups[i].first - groups[l].first; ikiL[i] = i - l + 1; kaimL[i] = dst; } } void calcToRight(int l, int r, int ind) { int dst = -1; if(ind != (int) interv.size() - 1) dst = abs(groups[interv[ind+1].first].first - groups[r].first); //cout << "calcToRight, ind = " << ind << ", dst = " << interv[ind+1].first << " - " << r << endl; for(int i = r; i >= l; i--) { toRight[i] = (i == r ? 0ll : toRight[i+1]) + groups[r].first - groups[i].first; ikiR[i] = r - i + 1; kaimR[i] = dst; } } long long min_total_length(vector<int> r, vector<int> b) { n = r.size() + b.size(); for(auto &x : r) { groups.push_back({x, 0}); } for(auto &x : b) { groups.push_back({x, 1}); } groupInd.resize(n); toLeft.resize(n); toRight.resize(n); ikiL.resize(n); ikiR.resize(n); kaimL.resize(n); kaimR.resize(n); sort(groups.begin(), groups.end()); for(int i = 0; i < n; i++) { for(int j = i; j <= n; j++) { if(j == n || groups[j].second != groups[i].second) { int l = i; int r = j-1; interv.push_back({l, r}); for(int h = l; h <= r; h++) { groupInd[h] = (int) interv.size()-1; } i = j-1; break; } } } for(int i = 0; i < interv.size(); i++) { int l = interv[i].first; int r = interv[i].second; calcToLeft(l, r, i); calcToRight(l, r, i); } /* cout << "intervalai: "; for(auto &x : interv) { cout << "(" << x.first << ", " << x.second << "), "; } cout << endl;*/ vector<long long> dp(n, inf); // dp[-1] = 0; for(int i = interv[1].first; i < n; i++) { int myInterv = groupInd[i]; dp[i] = dp[interv[myInterv-1].second] + f(interv[myInterv-1].second, i); for(int j = interv[myInterv-1].first; j <= interv[myInterv-1].second; j++) { dp[i] = min(dp[i], (j == 0 ? 0ll : dp[j-1]) + f(j, i)); // cout << "gali buti (nuo " << j << ") " << (j == 0 ? 0ll : dp[j-1]) << " + f(" << j << ", " << i << ") = " << f(j, i) << endl; } // cout << "dp[" << i << "] = " << dp[i] << endl << endl; } return dp[n-1]; }

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:70:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for(int i = 0; i < interv.size(); i++) {
      |                    ~~^~~~~~~~~~~~~~~
#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...