oj.uz

Submission #389623

# Submission time Handle Problem Language Result Execution time Memory
389623 2021-04-14T10:08:09 Z mariowong Collecting Stamps 3 (JOI20_ho_t3) C++14
0 / 100
 1 ms 716 KB 
#include <bits/stdc++.h>

using namespace std;

struct stamps{
	long long d,t;
}a[205];

long long dp[205][205][205][5],n,l,ans;
int main(){
	ios::sync_with_stdio(false);
	cin >> n >> l;
	for (int i=1;i<=n;i++){
		cin >> a[i].d;
	}
	for (int i=1;i<=n;i++){
		cin >> a[i].t;
	}
	for (int i=0;i<=n+1;i++){
		for (int j=0;j<=n+1;j++){
			for (int k=0;k<=n;k++){
				dp[i][j][k][0]=dp[i][j][k][1]=1e18;
			}
		}
	}
	a[n+1].d=l; 
	dp[0][n+1][0][0]=dp[0][n+1][0][1]=0;
	for (int i=0;i<=n;i++){
		for (int j=n+1;j>i;j--){
			for (int k=0;k<=max(0LL,n-j+1)+i;k++){
				if (i != 0){
					if (k > 0 && dp[i-1][j][k-1][0]+a[i].d-a[i-1].d <= a[i].t)
					dp[i][j][k][0]=min(dp[i][j][k][0],dp[i-1][j][k-1][0]+a[i].d-a[i-1].d);
					dp[i][j][k][0]=min(dp[i][j][k][0],dp[i-1][j][k][0]+a[i].d-a[i-1].d);
					
					if (k > 0 && j != n+1 && dp[i-1][j][k-1][1]+l-a[j].d+a[i].d <= a[i].t)
					dp[i][j][k][0]=min(dp[i][j][k][0],dp[i-1][j][k-1][1]+l-a[j].d+a[i].d);
					if (j != n+1)
					dp[i][j][k][0]=min(dp[i][j][k][0],dp[i-1][j][k][1]+l-a[j].d+a[i].d);
				}
				if (j != n+1){
					if (k > 0 && dp[i][j+1][k-1][1]+a[j+1].d-a[j].d <= a[j].t)
					dp[i][j][k][1]=min(dp[i][j][k][1],dp[i][j+1][k-1][1]+a[j+1].d-a[j].d);
					dp[i][j][k][1]=min(dp[i][j][k][1],dp[i][j+1][k][1]+a[j+1].d-a[j].d);
				//	cout << i << " " << j << " " << k << " " << dp[i][j+1][k-1][1] << " " << a[j+1].d<< " " << a[j].d << " " << l-a[j+1].d+a[j].d << "\n";
					if (k > 0 && i != 0 && dp[i][j-1][k-1][0]+l-a[j].d+a[i].d <= a[j].t)
					dp[i][j][k][1]=min(dp[i][j][k][1],dp[i][j+1][k-1][0]+l-a[j].d+a[i].d);
					if (i != 0)
					dp[i][j][k][1]=min(dp[i][j][k][1],dp[i][j+1][k][0]+l-a[j].d+a[i].d);
				}
			}
		}
	}
	for (int i=0;i<=n;i++){
		for (int j=n+1;j>i;j--){
			if (i+1 == j){
				for (long long k=1;k<=n;k++){
					if (dp[i][j][k][0] != 1e18 || dp[i][j][k][1] != 1e18)
					ans=max(ans,k);
				}
			}
		}
	}
	cout << ans << '\n'; 
	return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 464 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Incorrect 1 ms 588 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 464 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Incorrect 1 ms 588 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 464 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Incorrect 1 ms 588 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 464 KB Output is correct
3 Correct 1 ms 716 KB Output is correct
4 Correct 1 ms 588 KB Output is correct
5 Incorrect 1 ms 588 KB Output isn't correct
6 Halted 0 ms 0 KB -