Submission #445862

#	Time	Username	Problem	Language	Result	Execution time	Memory
445862		jamezzz	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	545 ms	135276 KiB

ho_t3

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

#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb emplace_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, int> li;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
mt19937 rng(time(0));

#define maxn 205

int n,l,x[maxn];ll t[maxn];
ll memo[maxn][maxn][maxn][2];

int dist(int a,int b){
	return min(abs(x[a]-x[b]),l-abs(x[a]-x[b]));
}

//visited from l to r, want to take k more, at side s
//returns earliest time u need to leave
ll dp(int l,int r,int k,int s){
	if(k==0)return LINF;
	if(r+1==l)return -LINF;
	if(memo[l][r][k][s]!=-1)return memo[l][r][k][s];
	ll res=-LINF;
	if(s==0){//at l
		res=max(res,min(t[l-1],dp(l-1,r,k-1,0))-dist(l-1,l));//go to left, take
		res=max(res,dp(l-1,r,k,0)-dist(l-1,l));//go to left, dont take
		res=max(res,min(t[r+1],dp(l,r+1,k-1,1))-dist(l,r+1));//go to right, take
		res=max(res,dp(l,r+1,k,1)-dist(l,r+1));//go to right, dont take
	}
	else{
		res=max(res,min(t[l-1],dp(l-1,r,k-1,0))-dist(l-1,r));//go to left, take
		res=max(res,dp(l-1,r,k,0)-dist(l-1,r));//go to left, dont take
		res=max(res,min(t[r+1],dp(l,r+1,k-1,1))-dist(r,r+1));//go to right, take
		res=max(res,dp(l,r+1,k,1)-dist(r,r+1));//go to right, dont take
	}
	return memo[l][r][k][s]=res;
}

int main(){
	sf("%d%d",&n,&l);
	for(int i=1;i<=n;++i){
		sf("%d",&x[i]);
	}
	for(int i=1;i<=n;++i){
		sf("%lld",&t[i]);
	}
	memset(memo,-1,sizeof memo);
	int ans=0;
	for(int k=0;k<=n;++k){
		if(dp(n+1,0,k,0)>=0)ans=k;
	}
	pf("%d\n",ans);
}

Compilation message (stderr)

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:57:4: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   57 |  sf("%d%d",&n,&l);
      |    ^
ho_t3.cpp:59:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   59 |   sf("%d",&x[i]);
      |     ^
ho_t3.cpp:62:5: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |   sf("%lld",&t[i]);
      |     ^

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