답안 #888026

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
888026	2023-12-15T19:36:59 Z	amirhoseinfar1385	Collecting Stamps 3 (JOI20_ho_t3)	C++17	15 / 100	47 ms	129568 KB

ho_t3

#include<bits/stdc++.h>
using namespace std;
const long long maxn=202,inf=1e15+10;
pair<long long,long long>dp[maxn][maxn][maxn];
long long n,allx[maxn],allt[maxn],L;

long long fas(long long a,long long b){
	long long ret=a-b;
	ret+=L;
	ret%=L;
	//cout<<a<<" "<<b<<" "<<ret<<" wtf"<<endl;
	return ret;
}

void upddp(long long l,long long r){
	//cout<<l<<" "<<r<<" "<<dp[l][r][0].first<<" "<<dp[l][r][0].second<<"\n";
	long long ll=(l-1)+n,rr=r+1;
	ll%=n;
	rr%=n;
	for(long long i=0;i<maxn;i++){
		if(dp[l][r][i].first!=inf){
			//cout<<l<<" "<<r<<" "<<i<<" "<<dp[l][r][i].first<<" "<<dp[l][r][i].second<<'\n';
			dp[ll][r][i].first=min(dp[ll][r][i].first,dp[l][r][i].first+fas(allx[l],allx[ll]));
			dp[ll][r][i].second=min(dp[ll][r][i].second,dp[ll][r][i].first+fas(allx[r],allx[ll]));
			if(fas(allx[l],allx[ll])+dp[l][r][i].first<=allt[ll]){
				dp[ll][r][i+1].first=min(dp[ll][r][i+1].first,dp[l][r][i].first+fas(allx[l],allx[ll]));
				dp[ll][r][i+1].second=min(dp[ll][r][i+1].second,dp[ll][r][i].first+fas(allx[r],allx[ll]));
			}
			dp[l][rr][i].second=min(dp[l][rr][i].second,dp[l][r][i].second+fas(allx[rr],allx[r]));
			dp[l][rr][i].first=min(dp[l][rr][i].first,dp[l][rr][i].second+fas(allx[rr],allx[l]));
			if(fas(allx[rr],allx[r])+dp[l][r][i].second<=allt[rr]){
				dp[l][rr][i+1].second=min(dp[l][rr][i].second,dp[l][r][i].second+fas(allx[rr],allx[r]));
				dp[l][rr][i+1].first=min(dp[l][rr][i+1].first,dp[l][rr][i+1].second+fas(allx[rr],allx[l]));
			}
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	for(long long i=0;i<maxn;i++){
		for(long long j=0;j<maxn;j++){
			for(long long h=0;h<maxn;h++){
				dp[i][j][h]=make_pair(inf,inf);
			}
		}
	}
	cin>>n>>L;
	for(long long i=0;i<n;i++){
		cin>>allx[i];
	}
	for(long long i=0;i<n;i++){
		cin>>allt[i];
	}
	if(allx[0]<=allt[0]){
		dp[0][0][0]=dp[0][0][1]=make_pair(allx[0],allx[0]);
	}
	else{
		dp[0][0][0]=make_pair(allx[0],allx[0]);
	}
	if(fas(0,allx[n-1])<=allt[n-1]){
		dp[n-1][n-1][0]=dp[n-1][n-1][1]=make_pair(fas(0,allx[n-1]),fas(0,allx[n-1]));
	}
	else{
		dp[n-1][n-1][0]=make_pair(fas(0,allx[n-1]),fas(0,allx[n-1]));
	}
	for(long long i=0;i<n-1;i++){
		upddp(0,0+i);
		for(long long l=n-1;l>=n-i-1;l--){
			upddp(l,(l+i)%n);
		}
	}
	long long res=0;
	for(long long i=0;i<maxn;i++){
		int j=i-1+n;
		j%=n;
			for(long long h=0;h<maxn;h++){
				if(dp[i][j][h].first!=inf){
					res=max(res,h);
				}
			}
	}
	cout<<res<<"\n";
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	129372 KB	Output is correct
2	Correct	18 ms	129372 KB	Output is correct
3	Correct	18 ms	129388 KB	Output is correct
4	Correct	18 ms	129280 KB	Output is correct
5	Correct	19 ms	129372 KB	Output is correct
6	Correct	18 ms	129368 KB	Output is correct
7	Correct	18 ms	129372 KB	Output is correct
8	Correct	18 ms	129448 KB	Output is correct
9	Correct	18 ms	129476 KB	Output is correct
10	Correct	18 ms	129352 KB	Output is correct
11	Correct	18 ms	129372 KB	Output is correct
12	Correct	18 ms	129288 KB	Output is correct
13	Correct	19 ms	129276 KB	Output is correct
14	Correct	19 ms	129360 KB	Output is correct
15	Correct	19 ms	129368 KB	Output is correct
16	Correct	19 ms	129496 KB	Output is correct
17	Correct	18 ms	129372 KB	Output is correct

Subtask #2
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	129372 KB	Output is correct
2	Correct	18 ms	129372 KB	Output is correct
3	Correct	18 ms	129388 KB	Output is correct
4	Correct	18 ms	129280 KB	Output is correct
5	Correct	19 ms	129372 KB	Output is correct
6	Correct	18 ms	129368 KB	Output is correct
7	Correct	18 ms	129372 KB	Output is correct
8	Correct	18 ms	129448 KB	Output is correct
9	Correct	18 ms	129476 KB	Output is correct
10	Correct	18 ms	129352 KB	Output is correct
11	Correct	18 ms	129372 KB	Output is correct
12	Correct	18 ms	129288 KB	Output is correct
13	Correct	19 ms	129276 KB	Output is correct
14	Correct	19 ms	129360 KB	Output is correct
15	Correct	19 ms	129368 KB	Output is correct
16	Correct	19 ms	129496 KB	Output is correct
17	Correct	18 ms	129372 KB	Output is correct
18	Correct	19 ms	129368 KB	Output is correct
19	Correct	18 ms	129372 KB	Output is correct
20	Correct	19 ms	129312 KB	Output is correct
21	Correct	18 ms	129372 KB	Output is correct
22	Correct	19 ms	129368 KB	Output is correct
23	Correct	19 ms	129368 KB	Output is correct
24	Correct	18 ms	129272 KB	Output is correct
25	Correct	19 ms	129368 KB	Output is correct
26	Correct	18 ms	129372 KB	Output is correct
27	Correct	18 ms	129568 KB	Output is correct
28	Correct	18 ms	129372 KB	Output is correct
29	Correct	18 ms	129384 KB	Output is correct
30	Correct	19 ms	129372 KB	Output is correct
31	Correct	18 ms	129372 KB	Output is correct
32	Correct	18 ms	129368 KB	Output is correct
33	Correct	18 ms	129372 KB	Output is correct
34	Correct	18 ms	129372 KB	Output is correct
35	Correct	19 ms	129280 KB	Output is correct

Subtask #3
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	129372 KB	Output is correct
2	Correct	18 ms	129372 KB	Output is correct
3	Correct	18 ms	129388 KB	Output is correct
4	Correct	18 ms	129280 KB	Output is correct
5	Correct	19 ms	129372 KB	Output is correct
6	Correct	18 ms	129368 KB	Output is correct
7	Correct	18 ms	129372 KB	Output is correct
8	Correct	18 ms	129448 KB	Output is correct
9	Correct	18 ms	129476 KB	Output is correct
10	Correct	18 ms	129352 KB	Output is correct
11	Correct	18 ms	129372 KB	Output is correct
12	Correct	18 ms	129288 KB	Output is correct
13	Correct	19 ms	129276 KB	Output is correct
14	Correct	19 ms	129360 KB	Output is correct
15	Correct	19 ms	129368 KB	Output is correct
16	Correct	19 ms	129496 KB	Output is correct
17	Correct	18 ms	129372 KB	Output is correct
18	Correct	47 ms	129536 KB	Output is correct
19	Correct	33 ms	129372 KB	Output is correct
20	Incorrect	24 ms	129540 KB	Output isn't correct
21	Halted	0 ms	0 KB	-

Subtask #4
0 / 75.0

#	결과	실행 시간	메모리	Grader output
1	Correct	22 ms	129372 KB	Output is correct
2	Correct	18 ms	129372 KB	Output is correct
3	Correct	18 ms	129388 KB	Output is correct
4	Correct	18 ms	129280 KB	Output is correct
5	Correct	19 ms	129372 KB	Output is correct
6	Correct	18 ms	129368 KB	Output is correct
7	Correct	18 ms	129372 KB	Output is correct
8	Correct	18 ms	129448 KB	Output is correct
9	Correct	18 ms	129476 KB	Output is correct
10	Correct	18 ms	129352 KB	Output is correct
11	Correct	18 ms	129372 KB	Output is correct
12	Correct	18 ms	129288 KB	Output is correct
13	Correct	19 ms	129276 KB	Output is correct
14	Correct	19 ms	129360 KB	Output is correct
15	Correct	19 ms	129368 KB	Output is correct
16	Correct	19 ms	129496 KB	Output is correct
17	Correct	18 ms	129372 KB	Output is correct
18	Correct	19 ms	129368 KB	Output is correct
19	Correct	18 ms	129372 KB	Output is correct
20	Correct	19 ms	129312 KB	Output is correct
21	Correct	18 ms	129372 KB	Output is correct
22	Correct	19 ms	129368 KB	Output is correct
23	Correct	19 ms	129368 KB	Output is correct
24	Correct	18 ms	129272 KB	Output is correct
25	Correct	19 ms	129368 KB	Output is correct
26	Correct	18 ms	129372 KB	Output is correct
27	Correct	18 ms	129568 KB	Output is correct
28	Correct	18 ms	129372 KB	Output is correct
29	Correct	18 ms	129384 KB	Output is correct
30	Correct	19 ms	129372 KB	Output is correct
31	Correct	18 ms	129372 KB	Output is correct
32	Correct	18 ms	129368 KB	Output is correct
33	Correct	18 ms	129372 KB	Output is correct
34	Correct	18 ms	129372 KB	Output is correct
35	Correct	19 ms	129280 KB	Output is correct
36	Correct	47 ms	129536 KB	Output is correct
37	Correct	33 ms	129372 KB	Output is correct
38	Incorrect	24 ms	129540 KB	Output isn't correct
39	Halted	0 ms	0 KB	-

답안 #888026

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 10.0 / 10.0

Subtask #3 0 / 10.0

Subtask #4 0 / 75.0

Subtask #1
5.0 / 5.0

Subtask #2
10.0 / 10.0

Subtask #3
0 / 10.0

Subtask #4
0 / 75.0