Submission #201591

#	Time	Username	Problem	Language	Result	Execution time	Memory
201591		MvC	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	161 ms	128888 KiB

ho_t3

#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=2e2+2;
const int mod=1e9+7;
using namespace std;
int i,j,k,p,rs,n;
ll t[nmax],r[nmax],a[nmax],b[nmax],f[nmax][nmax][nmax][2],l;
ll d1(int i,int j)
{
	return a[j]-a[i];
}
ll d2(int i,int j)
{
	return b[j]-b[i];
}
void upd(ll &x,ll y,ll z)
{
	if(y>=llinf)return;
	x=min(x,y+z);
}
void upd1(ll &x,ll y,ll z,ll p,ll tt)
{
	if(y>=llinf)return;
	if(y+z<=tt)x=min(x,y+z+p);
}
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n>>l;
	for(i=1;i<=n;i++)
	{
		cin>>a[i];
		b[n-i+1]=l-a[i];
	}
	for(i=1;i<=n;i++)
	{
		cin>>t[i];
		r[n-i+1]=t[i];
	}
	for(i=0;i<=n;i++)for(j=0;j<=n;j++)for(k=0;k<=n;k++)for(p=0;p<2;p++)f[i][j][k][p]=llinf;
	f[0][0][0][0]=f[0][0][0][1]=0;
	for(i=0;i<=n;i++)
	{
		for(j=0;j<=n-i;j++)
		{
			for(k=0;k<=i+j;k++)
			{
				if(!i && !j)continue;
				if(j)upd(f[i][j][k][0],f[i][j-1][k][1],d1(0,i)+d2(j-1,j)+d2(0,j));
				if(j)upd(f[i][j][k][0],f[i][j-1][k][0],d1(0,i)+d1(0,i)+d2(0,j)+d2(0,j));
				if(i)upd(f[i][j][k][0],f[i-1][j][k][1],d2(0,j)+d1(0,i));
				if(i)upd(f[i][j][k][0],f[i-1][j][k][0],d1(i-1,i));
				if(j && k)upd1(f[i][j][k][0],f[i][j-1][k-1][1],d2(j-1,j),d1(0,i)+d2(0,j),r[j]);
				if(j && k)upd1(f[i][j][k][0],f[i][j-1][k-1][0],d1(0,i)+d2(0,j),d1(0,i)+d2(0,j),r[j]);
				if(i && k)upd1(f[i][j][k][0],f[i-1][j][k-1][1],d2(0,j)+d1(0,i),0,t[i]);
				if(i && k)upd1(f[i][j][k][0],f[i-1][j][k-1][0],d1(i-1,i),0,t[i]);
				
				if(j)upd(f[i][j][k][1],f[i][j-1][k][1],d2(j-1,j));
				if(j)upd(f[i][j][k][1],f[i][j-1][k][0],d1(0,i)+d2(0,j));
				if(i)upd(f[i][j][k][1],f[i-1][j][k][1],d2(0,j)+d1(0,i)+d1(0,i)+d2(0,j));
				if(i)upd(f[i][j][k][1],f[i-1][j][k][0],d1(i-1,i)+d1(0,i)+d2(0,j));
				if(j && k)upd1(f[i][j][k][1],f[i][j-1][k-1][1],d2(j-1,j),0,r[j]);
				if(j && k)upd1(f[i][j][k][1],f[i][j-1][k-1][0],d1(0,i)+d2(0,j),0,r[j]);
				if(i && k)upd1(f[i][j][k][1],f[i-1][j][k-1][1],d2(0,j)+d1(0,i),d2(0,j)+d1(0,i),t[i]);
				if(i && k)upd1(f[i][j][k][1],f[i-1][j][k-1][0],d1(i-1,i),d1(0,i)+d2(0,j),t[i]);
				if(f[i][j][k][0]!=llinf || f[i][j][k][1]!=llinf)rs=max(rs,k);
			}
		}
	}
	cout<<rs<<endl;
	return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 75 / 75