Submission #640595

#	Time	Username	Problem	Language	Result	Execution time	Memory
640595		ggoh	Wiring (IOI17_wiring)	C++14	0 / 100	2 ms	2772 KiB

wiring

#include "wiring.h"
#include<bits/stdc++.h>
using namespace std;
#define sz(v) ((int)(v).size())
typedef long long lint;
typedef pair<int,int> pii;
 
int rec[200002][2];
int n,m;
lint D[402][402][2];
vector<pii>V;
 
lint f(int p,int q,int r)
{
	if(D[p][q][r]>=0)return D[p][q][r];
	if(p<q)return D[p][q][r]=1e18;
	if(p==0)return D[p][q][r]=0;
	if(q==0)
	{
		D[p][q][r]=1e18;
		int ind=rec[p][1-V[p].second];
		if(ind!=-1)
		{	
			D[p][q][r]=min(D[p][q][r],V[p].first-V[ind].first+f(p-1,0,0));
			lint sum=0;
			for(int i=1;i<=p-1;i++)
			{
				if(ind<=0)break;
				sum+=V[p].first-V[ind].first;
				D[p][q][r]=min(D[p][q][r],sum+f(p-1,i,V[ind].second));
				ind=rec[ind-1][V[ind].second];
			}
		}
		return D[p][q][r];
	}
	else
	{
		if(r==V[p].second)return D[p][q][r]=f(p-1,q-1,q==1?0:r);
		else
		{
			int ind=p;
			for(int i=0;i<=q;i++)
			{
				ind=rec[ind-1][r];
				if(ind==-1)break;
			}
			if(ind==-1)return D[p][q][r]=1e18;
			else return D[p][q][r]=f(p-1,q+1,r)+V[p].first-V[ind].first;
		}
	}
}
lint min_total_length(vector<int> r, vector<int> b) {
  lint ans=0;
  n=sz(r),m=sz(b);
  for(int i=0;i<n;i++)V.push_back({r[i],0});
  for(int j=0;j<m;j++)V.push_back({b[j],1});
  V.push_back({-1e9,0});
  sort(V.begin(),V.end());
  n=sz(V)-1;
  rec[0][0]=rec[0][1]=-1;
  for(int i=1;i<=n;i++)
  {
	rec[i][0]=rec[i-1][0];
	rec[i][1]=rec[i-1][1];
	rec[i][V[i].second]=i;
  }
  memset(D,-1,sizeof(D));
  ans=f(n,0,0);
  return ans;
}

Compilation message (stderr)

wiring.cpp: In function 'lint _Z1fiii.part.0(int, int, int)':
wiring.cpp:16:19: warning: array subscript -1 is below array bounds of 'lint [402][402][2]' {aka 'long long int [402][402][2]'} [-Warray-bounds]
   16 |  if(p<q)return D[p][q][r]=1e18;
      |                ~~~^
wiring.cpp:10:6: note: while referencing 'D'
   10 | lint D[402][402][2];
      |      ^
wiring.cpp: In function 'lint min_total_length(std::vector<int>, std::vector<int>)':
wiring.cpp:16:19: warning: array subscript -1 is below array bounds of 'lint [402][402][2]' {aka 'long long int [402][402][2]'} [-Warray-bounds]
   16 |  if(p<q)return D[p][q][r]=1e18;
      |                ~~~^

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