Submission #660599

#	Time	Username	Problem	Language	Result	Execution time	Memory
660599		Trisanu_Das	Wiring (IOI17_wiring)	C++17	0 / 100	1079 ms	9224 KiB

wiring

#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;
      |                        ^~

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