oj.uz

답안 #222543

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
222543 2020-04-13T09:51:56 Z astoria Collecting Stamps 3 (JOI20_ho_t3) C++14
0 / 100
 5 ms 384 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main(){
	int n,l;
	cin>>n>>l;
	int x[n+5],t[n+5];
	for(int i=1; i<=n; i++) cin>>x[i];
	for(int i=1; i<=n; i++) cin>>t[i];
	x[n+1] = l;
	
	int dp[n+5][n+5][n+5][2];
	for(int i=0; i<n+5; i++){
		for(int j=0; j<n+5; j++){
			for(int k=0; k<n+5; k++){
				dp[i][j][k][0]=1e17; dp[i][j][k][1]=1e17;
			}
		}
	} //fill
	
	dp[0][n+1][0][0] = 0;
	dp[0][n+1][0][1] = 0;
	
	int at0[n+5];
	
	fill(at0,at0+n+5,1e17);
	at0[0] = 0;
	for(int k=0; k<=n; k++){
		for(int j=n; j>0; j--){
			dp[0][j][k][1] = min(dp[0][j+1][k][1] + (x[j+1]-x[j]), dp[0][j][k][1]);
			if(k!=0){
				if(dp[0][j+1][k-1][1] + (x[j+1]-x[j]) <= t[j]){
					dp[0][j][k][1] = min(dp[0][j+1][k-1][1] + (x[j+1]-x[j]), dp[0][j][k][1]);
				}
				if(at0[k-1] + l-x[j] <= t[j]){
					dp[0][j][k][1] = min(dp[0][j][k][1], at0[k-1] + l-x[j]);
				}
			}
		}
		for(int i=1; i<=n; i++){
			dp[i][n+1][k][0] = min(dp[i-1][n+1][k][0] + (x[i]-x[i-1]), dp[i][n+1][k][0]);
			if(k!=0){
				if(dp[i-1][n+1][k-1][0] + (x[i]-x[i-1]) <= t[i]){
					dp[i][n+1][k][0] = min(dp[i-1][n+1][k-1][0] + (x[i]-x[i-1]), dp[i][n+1][k][0]);
				}
				if(at0[k-1] + x[i] <= t[i]){
					dp[i][n+1][k][0] = min(dp[i][n+1][k][0], at0[k-1] + x[i]);
				}
			}
			for(int j=n; j>i; j--){
				dp[i][j][k][1] = min(dp[i][j+1][k][1] + (x[j+1]-x[j]), dp[i][j][k][1]);
				dp[i][j][k][0] = min(dp[i-1][j][k][0] + (x[i]-x[i-1]), dp[i][j][k][0]);
				if(k!=0){
					if(dp[i][j+1][k-1][1] + (x[j+1]-x[j]) <= t[j]){
						dp[i][j][k][1] = min(dp[i][j+1][k-1][1] + (x[j+1]-x[j]), dp[i][j][k][1]);
					}
					if(dp[i-1][j][k-1][0] + (x[i]-x[i-1]) <= t[i]){
						dp[i][j][k][0] = min(dp[i-1][j][k-1][0] + (x[i]-x[i-1]), dp[i][j][k][0]);
					}
					if(at0[k-1] + l-x[j] <= t[j]){
						dp[i][j][k][1] = min(dp[i][j][k][1], at0[k-1] + l-x[j]);
					}
					if(at0[k-1] + x[i] <= t[i]){
						dp[i][j][k][0] = min(dp[i][j][k][0], at0[k-1] + x[i]);
					}
				}
				dp[i][j][k][0] = min(dp[i][j][k][0], at0[k]+x[i]);
				dp[i][j][k][1] = min(dp[i][j][k][1], at0[k]+l-x[j]);
				
				at0[k] = min(at0[k], dp[i][j][k][1] + l-x[j]);
				at0[k] = min(at0[k], dp[i][j][k][0] + x[i]);
			}
		}
		//cout<<at0[k]<<endl;
	}
	
	int an=0;
	for(int i=0; i<=n; i++){
		for(int j=0; j<=n; j++){
			for(int k=1; k<=n; k++){
				if(dp[i][j][k][0]<1e15 || dp[i][j][k][1]<1e15) an=max(an,k);
			}
		}
	}
	cout<<an;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -