Submission #545169

#	Time	Username	Problem	Language	Result	Execution time	Memory
545169		MilosMilutinovic	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	263 ms	130772 KiB

ho_t3

#include<bits/stdc++.h>

#define fi first
#define se second
#define pb push_back
#define mp make_pair

using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

template<typename T> bool chkmin(T&x,T y){return x>y?x=y,1:0;}
template<typename T> bool chkmax(T&x,T y){return x<y?x=y,1:0;}

int n,k,a[205],t[205];
ll dp[205][205][205][2];

int main(){
	scanf("%d%d",&n,&k);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) scanf("%d",&t[i]);
	for(int i=0;i<=n;i++) for(int l=0;l<=n;l++) for(int r=0;r<=n;r++) dp[l][r][i][0]=dp[l][r][i][1]=1e18;
	dp[0][0][0][0]=dp[0][0][0][1]=0;
	for(int i=0;i<n;i++) for(int l=0;l<=n;l++) for(int r=0;r<=n;r++) if(l+r<n) for(int st=0;st<2;st++) {
		{
			//left
			ll nt=dp[i][l][r][st]+(st==0?a[l+1]-a[l]:k-a[n+1-r]+a[l+1]);
			chkmin(dp[i+(nt<=t[l+1])][l+1][r][0],nt);
		}
		{
			//right
			ll nt=dp[i][l][r][st]+(st==0?a[l]+k-a[n-r]:(a[n+1-r]-a[n-r]+k)%k);
			chkmin(dp[i+(nt<=t[n-r])][l][r+1][1],nt);
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++) for(int l=0;l<=n;l++) for(int r=0;r<=n;r++) if(dp[i][l][r][0]!=1e18|dp[i][l][r][1]!=1e18) ans=i;
	printf("%d",ans);
	return 0;
}

Compilation message (stderr)

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:40:85: warning: suggest parentheses around comparison in operand of '|' [-Wparentheses]
   40 |  for(int i=1;i<=n;i++) for(int l=0;l<=n;l++) for(int r=0;r<=n;r++) if(dp[i][l][r][0]!=1e18|dp[i][l][r][1]!=1e18) ans=i;
      |                                                                       ~~~~~~~~~~~~~~^~~~~~
ho_t3.cpp:22:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |  scanf("%d%d",&n,&k);
      |  ~~~~~^~~~~~~~~~~~~~
ho_t3.cpp:23:29: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |  for(int i=1;i<=n;i++) scanf("%d",&a[i]);
      |                        ~~~~~^~~~~~~~~~~~
ho_t3.cpp:24:29: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |  for(int i=1;i<=n;i++) scanf("%d",&t[i]);
      |                        ~~~~~^~~~~~~~~~~~

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