Submission #640610

#	Time	Username	Problem	Language	Result	Execution time	Memory
640610		ggoh	Wiring (IOI17_wiring)	C++14	10 / 100	95 ms	53988 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[200002][7][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<=6;i++)
			{
				if(ind-i+1<=0 || V[ind-i+1].second==V[p].second)break;
				sum+=V[p].first-V[ind-i+1].first;
				D[p][q][r]=min(D[p][q][r],sum+f(p-1,i,V[ind].second));
			}
		}
		return D[p][q][r];
	}
	else
	{
		if(r==V[p].second)
		{
			if(q==1)return D[p][q][r]=f(p-1,0,0);
			else
			{
				if(V[p].second!=V[p-1].second)return D[p][q][r]=1e18;
				else return D[p][q][r]=f(p-1,q-1,r);
			}
		}
		else
		{
			int ind=rec[p][r];
			D[p][q][r]=1e18;
			if(ind!=-1)
			{
				for(int i=1;i<=q;i++)
				{
					if(ind-i+1<=0 || V[ind-i+1].second==V[p].second)return D[p][q][r]=1e18;
				}
				lint sum=0;
				for(int i=q+1;i<=6;i++)
				{
					if(ind-i+1<=0 || V[ind-i+1].second==V[p].second)break;
					sum+=V[p].first-V[ind-i+1].first;
					D[p][q][r]=min(D[p][q][r],sum+f(p-1,i,r));
				}
			}
			return D[p][q][r];
		}
	}
}
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);
  //for(int i=1;i<=n;i++)for(int j=0;j<7;j++)printf("%d %d %lld %lld\n",i,j,D[i][j][0],D[i][j][1]);
  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 [200002][7][2]' {aka 'long long int [200002][7][2]'} [-Warray-bounds]
   16 |  if(p<q)return D[p][q][r]=1e18;
      |                ~~~^
wiring.cpp:10:6: note: while referencing 'D'
   10 | lint D[200002][7][2];
      |      ^
wiring.cpp:16:19: warning: array subscript -1 is below array bounds of 'lint [200002][7][2]' {aka 'long long int [200002][7][2]'} [-Warray-bounds]
   16 |  if(p<q)return D[p][q][r]=1e18;
      |                ~~~^
wiring.cpp:10:6: note: while referencing 'D'
   10 | lint D[200002][7][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 [200002][7][2]' {aka 'long long int [200002][7][2]'} [-Warray-bounds]
   16 |  if(p<q)return D[p][q][r]=1e18;
      |                ~~~^

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