Submission #660599

#TimeUsernameProblemLanguageResultExecution timeMemory
660599Trisanu_DasWiring (IOI17_wiring)C++17
0 / 100
1079 ms9224 KiB
#include <bits/stdc++.h> using namespace std; #define mp make_pair #define pb push_back #define a first #define b second #include "wiring.h" long long dp[200001]; long long dp2[200001]; long long min_total_length(std::vector<int> r, std::vector<int> b) { vector<pair<int,int>> ss; int n = r.size(); int m = b.size(); for(long long i = 0;i<n;i++) ss.pb({r[i],0}); for(long long i = 0;i<m;i++) ss.pb({b[i],1}); vector<vector<long long>> tt; sort(ss.begin(),ss.end()); int ind2 = 0; while(ind2<ss.size()){ int cur = ss[ind2].b; tt.pb({}); while(ind2<ss.size()){ if(ss[ind2].b == cur){ tt[tt.size() - 1].pb(ss[ind2].a); ind2++; } else break; } } for(long long i = 0;i <= n+m;i++) dp[i] = 1e18; dp[0] = 0;; for(long long i = 1;i<tt.size();i++){ for(long long j = 0;j <= tt[i].size();j++) dp2[j] = 1e18; vector<long long> mi; vector<long long> mi2; for(long long j = 0;j <= tt[i - 1].size();j++){ mi.pb((long long)1e18); mi2.pb((long long)1e18); } long long xx = tt[i - 1].size(); long long su = 0; long long ind = xx - 1; for(long long j = 0;j <= tt[i - 1].size();j++){ if(j>0){ su += tt[i - 1][ind]; ind--; } mi[j] = min(mi[j],dp[xx - j]+tt[i - 1].back()*j - su); if(j>0) mi[j] = min(mi[j - 1],mi[j]); } ind = 0; for(long long j = tt[i - 1].size();j >= 0;j--){ mi2[j] = min(mi2[j],dp[xx - j] - su+tt[i][0]*j); if(j<tt[i - 1].size()) mi2[j] = min(mi2[j],mi2[j+1]); if(j>0){ su -= tt[i - 1][ind]; ind++; } } long long kk = 0; for(long long j = 0;j <= tt[i].size();j++){ if(j > 0) kk += tt[i][j - 1]; dp2[j] = min(dp2[j],mi[min(j,(long long)xx)] - tt[i - 1].back()*j+kk); if(j <= xx) dp2[j] = min(dp2[j],mi2[j] - tt[i][0]*j+kk); for(long long j = 0;j <= tt[i].size();j++) dp[j] = dp2[j]; } return dp[tt.back().size()]; } }

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:20:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |  while(ind2<ss.size()){
      |        ~~~~^~~~~~~~~~
wiring.cpp:23:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |   while(ind2<ss.size()){
      |         ~~~~^~~~~~~~~~
wiring.cpp:33:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::vector<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |  for(long long i = 1;i<tt.size();i++){
      |                      ~^~~~~~~~~~
wiring.cpp:34:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |   for(long long j = 0;j <= tt[i].size();j++) dp2[j] = 1e18;
      |                       ~~^~~~~~~~~~~~~~~
wiring.cpp:37:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |   for(long long j = 0;j <= tt[i - 1].size();j++){
      |                       ~~^~~~~~~~~~~~~~~~~~~
wiring.cpp:44:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   for(long long j = 0;j <= tt[i - 1].size();j++){
      |                       ~~^~~~~~~~~~~~~~~~~~~
wiring.cpp:55:8: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |    if(j<tt[i - 1].size()) mi2[j] = min(mi2[j],mi2[j+1]);
      |       ~^~~~~~~~~~~~~~~~~
wiring.cpp:62:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |   for(long long j = 0;j <= tt[i].size();j++){
      |                       ~~^~~~~~~~~~~~~~~
wiring.cpp:66:25: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |   for(long long j = 0;j <= tt[i].size();j++) dp[j] = dp2[j];
      |                       ~~^~~~~~~~~~~~~~~
wiring.cpp:12:24: warning: control reaches end of non-void function [-Wreturn-type]
   12 |  vector<pair<int,int>> ss;
      |                        ^~
#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...