Submission #71889

#	Time	Username	Problem	Language	Result	Execution time	Memory
71889		zetapi	Wiring (IOI17_wiring)	C++14	100 / 100	97 ms	76020 KiB

wiring

//#include <wiring.h>
#include <bits/stdc++.h>
using namespace std;

#define pb  push_back
#define mp  make_pair
#define ll  long long
#define itr ::iterator 

typedef pair<ll,ll>  pii;

const ll MAX=3e5;
const ll INF=1e17;

vector<pii> vec,blocks;

ll arr[MAX],dp[MAX],Min[MAX],Max[MAX];

void relax(int idx)
{
   ll cur=0;
   for(int A=blocks[idx].second;A>=blocks[idx].first;A--)
   {
      cur+=arr[blocks[idx].second]-arr[A];
      Min[A]=min(dp[A],dp[A-1])+cur;
      Max[A]=min(dp[A],dp[A-1])+cur+(blocks[idx].second-A+1)*(arr[blocks[idx+1].first]-arr[blocks[idx].second]);
      assert(Min[A]>=0);
      assert(Max[A]>=0);
   }
   for(int A=blocks[idx].second-1;A>=blocks[idx].first;A--)
      Min[A]=min(Min[A],Min[A+1]);
   for(int A=blocks[idx].first+1;A<=blocks[idx].second;A++)
      Max[A]=min(Max[A],Max[A-1]);
   return ;
}

ll min_total_length(vector<int> r={1,2,3,7},vector<int> b={0,4,5,9,10}) 
{  
   for(int A=0;A<r.size();A++)
      vec.pb(mp(r[A],0));
   for(int A=0;A<b.size();A++)
      vec.pb(mp(b[A],1));
   sort(vec.begin(),vec.end());
   for(int A=0;A<vec.size();A++)
      arr[A+1]=vec[A].first;
   ll cur=0;
   for(int A=1;A<vec.size();A++)
   {
      if(vec[A].second!=vec[A-1].second)
      {
         blocks.pb(mp(cur+1,A-1+1));
         cur=A;
      }
   }
   blocks.pb(mp(cur+1,vec.size()-1+1));
   /*for(auto A:blocks)
      cout<<A.first<<" "<<A.second<<"\n";*/
   cur=0;
   for(int A=blocks[0].first;A<=blocks[0].second;A++)
   {
      dp[A]=INF;
      cur+=arr[blocks[0].second]-arr[A];
   }
   for(int A=blocks[1].first;A<=blocks[1].second;A++)
   {
      cur+=arr[A]-arr[blocks[1].first];
      dp[A]=cur+max(A-blocks[1].first+1,blocks[0].second-blocks[0].first+1)*(arr[blocks[1].first]-arr[blocks[0].second]);
   }
   for(int A=2;A<blocks.size();A++)
   {
      relax(A-1);
      cur=0;
      for(int B=blocks[A].first;B<=blocks[A].second;B++)
      {
         dp[B]=INF;
         cur+=arr[B]-arr[blocks[A].first];
         ll actual=B-blocks[A].first,C=blocks[A-1].second-actual;
         if(blocks[A-1].second-actual>=blocks[A-1].first)
         {
            dp[B]=min(dp[B],cur+Max[C]);
            dp[B]=min(dp[B],cur+Min[C]+(arr[blocks[A].first]-arr[blocks[A-1].second])*(actual+1));
         }
         else
            dp[B]=min(dp[B],cur+Min[blocks[A-1].first]+(arr[blocks[A].first]-arr[blocks[A-1].second])*(actual+1));
      }
   }
   return dp[vec.size()];
}

/*signed main()
{
   ios_base::sync_with_stdio(false);

   cout<<min_total_length();
   return 0;
}*/

Compilation message (stderr)

wiring.cpp: In function 'long long int min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:39:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int A=0;A<r.size();A++)
                ~^~~~~~~~~
wiring.cpp:41:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int A=0;A<b.size();A++)
                ~^~~~~~~~~
wiring.cpp:44:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int A=0;A<vec.size();A++)
                ~^~~~~~~~~~~
wiring.cpp:47:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int A=1;A<vec.size();A++)
                ~^~~~~~~~~~~
wiring.cpp:69:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int A=2;A<blocks.size();A++)
                ~^~~~~~~~~~~~~~

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