oj.uz

Submission #959813

# Submission time Handle Problem Language Result Execution time Memory
959813 2024-04-09T07:14:44 Z happy_node Collecting Stamps 3 (JOI20_ho_t3) C++17
0 / 100
 77 ms 135184 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MX=205;

ll N,L;
ll X[MX], T[MX], dp[MX][MX][MX][2];

int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);

	for(int i=0;i<MX;i++)
		for(int j=0;j<MX;j++)
			for(int x=0;x<MX;x++)
				for(int k=0;k<2;k++)
					dp[i][j][x][k]=1e18;

	cin>>N>>L;
	for(int i=1;i<=N;i++) cin>>X[i];
	for(int i=1;i<=N;i++) cin>>T[i];

	dp[0][N+1][0][0]=0;
	dp[0][N+1][0][1]=0;
	X[N+1]=L;

	for(int l=0;l<=N;l++) {
		for(int r=N+1;r>l;r--) {
			for(int x=0;x<=N;x++) {
				// gerakin kanan
				ll nxt=dp[l][r][x][0]+X[l+1]-X[l];
				if(nxt<=T[l+1])
					dp[l+1][r][x+1][0]=min(dp[l+1][r][x+1][0],nxt);
				else
					dp[l+1][r][x][0]=min(dp[l+1][r][x][0],nxt);

				nxt=dp[l][r][x][1]+L-X[r]+X[l+1];
				if(nxt<=T[l+1])
					dp[l+1][r][x+1][0]=min(dp[l+1][r][x+1][0],nxt);
				else
					dp[l+1][r][x][0]=min(dp[l+1][r][x][0],nxt);

				// gerakin kiri
				nxt=dp[l][r][x][1]+X[r]-X[r-1];
				if(nxt<=T[r-1]) 
					dp[l][r-1][x+1][1]=min(dp[l][r-1][x+1][1],nxt);

				nxt=dp[l][r][x][0]+X[l]+L-X[r-1];
				if(nxt<=T[r-1])
					dp[l][r-1][x+1][1]=min(dp[l][r-1][x+1][1],nxt);
				else
					dp[l][r-1][x][1]=min(dp[l][r-1][x][1],nxt);
			}
		}
	}
	
	int ans=0;

	for(int l=0;l<=N;l++) {
		for(int r=N+1;r>l;r--) {
			for(int x=0;x<=N;x++) {
				if(min(dp[l][r][x][0],dp[l][r][x][1])!=1e18)
					ans=max(ans,x);
			}
		}
	}

	cout<<ans<<'\n';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 77 ms 135184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 77 ms 135184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 77 ms 135184 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Incorrect 77 ms 135184 KB Output isn't correct
2 Halted 0 ms 0 KB -