oj.uz

Submission #724705

# Submission time Handle Problem Language Result Execution time Memory
724705 2023-04-15T18:02:34 Z vjudge1 Collecting Stamps 3 (JOI20_ho_t3) C++17
15 / 100
 4 ms 4472 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define fi first
#define se second
#define pb push_back
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5+10;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int main(){
  	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    // freopen("shuffle.in","r",stdin);
    // freopen("shuffle.out","w",stdout);

	int n; ll l; cin >> n >> l;

	vector<ll> arr, tempo;
	for(int i=0;i<n;i++){
		ll x; cin >> x;
		arr.pb(x);
	}
	arr.pb(l);
	for(int i=0;i<n;i++) arr.pb(arr[i]+l);

	tempo.resize(2*n+1);
	for(int i=0;i<n;i++) cin >> tempo[i];
	for(int i=0;i<n;i++) tempo[i+n+1]=tempo[i];
	tempo[n]=-1;

	ll dp[25][25][405];
	for(int i=0;i<=n;i++)
		for(int j=0;j<=n;j++)
			for(int k=0;k<=2*n;k++) 
				dp[i][j][k]=INF;
	dp[0][0][n]=0;

	int ans=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<=i;j++){
			for(int pos=0;pos<=2*n;pos++){
				if(dp[i][j][pos]==INF) continue;
				int nxd, nxu;

				if(pos>n){
					nxu=pos+1;
					nxd=nxu-i-2;
				}
				else{
					nxd=pos-1;
					nxu=nxd+i+2;
				}

				// cout << i << " " << pos << " " << nxd << " " << nxu << "\n";

				// if(j==3) cout << i << " " << pos << " " << nxd << " " << nxu << "\n";

				ll curr=dp[i][j][pos]+abs(arr[pos]-arr[nxd]);
				if(nxd>=0 && tempo[nxd]>=curr){
					// if(j+1==5) cout << i << " " << pos << " " << nxd << " " << nxu << "\n";
					ans=max(ans, j+1);
					dp[i+1][j+1][nxd]=min(dp[i+1][j+1][nxd], curr);
				}
				else if(nxd>=0) dp[i+1][j][nxd]=min(dp[i+1][j][nxd], curr);

				curr=dp[i][j][pos]+abs(arr[pos]-arr[nxu]);
				if(nxu<=2*n && tempo[nxu]>=curr){
					// if(j+1==5) cout << i << " " << pos << " " << nxd << " " << nxu << "\n";
					ans=max(ans, j+1);
					dp[i+1][j+1][nxu]=min(dp[i+1][j+1][nxu], curr);
				}
				else if(nxu<=2*n) dp[i+1][j][nxu]=min(dp[i+1][j][nxu], curr);
			}
		}
	}

	cout << ans << "\n";
	return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2260 KB Output is correct
2 Correct 1 ms 2260 KB Output is correct
3 Correct 1 ms 2260 KB Output is correct
4 Correct 1 ms 2260 KB Output is correct
5 Correct 2 ms 2260 KB Output is correct
6 Correct 2 ms 2260 KB Output is correct
7 Correct 1 ms 2260 KB Output is correct
8 Correct 2 ms 2260 KB Output is correct
9 Correct 1 ms 2260 KB Output is correct
10 Correct 1 ms 2260 KB Output is correct
11 Correct 1 ms 2260 KB Output is correct
12 Correct 1 ms 2260 KB Output is correct
13 Correct 1 ms 2260 KB Output is correct
14 Correct 1 ms 2260 KB Output is correct
15 Correct 1 ms 2260 KB Output is correct
16 Correct 1 ms 2260 KB Output is correct
17 Correct 1 ms 2260 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2260 KB Output is correct
2 Correct 1 ms 2260 KB Output is correct
3 Correct 1 ms 2260 KB Output is correct
4 Correct 1 ms 2260 KB Output is correct
5 Correct 2 ms 2260 KB Output is correct
6 Correct 2 ms 2260 KB Output is correct
7 Correct 1 ms 2260 KB Output is correct
8 Correct 2 ms 2260 KB Output is correct
9 Correct 1 ms 2260 KB Output is correct
10 Correct 1 ms 2260 KB Output is correct
11 Correct 1 ms 2260 KB Output is correct
12 Correct 1 ms 2260 KB Output is correct
13 Correct 1 ms 2260 KB Output is correct
14 Correct 1 ms 2260 KB Output is correct
15 Correct 1 ms 2260 KB Output is correct
16 Correct 1 ms 2260 KB Output is correct
17 Correct 1 ms 2260 KB Output is correct
18 Correct 1 ms 2260 KB Output is correct
19 Correct 1 ms 2260 KB Output is correct
20 Correct 1 ms 2260 KB Output is correct
21 Correct 1 ms 2292 KB Output is correct
22 Correct 1 ms 2260 KB Output is correct
23 Correct 2 ms 2300 KB Output is correct
24 Correct 2 ms 2304 KB Output is correct
25 Correct 1 ms 2260 KB Output is correct
26 Correct 1 ms 2260 KB Output is correct
27 Correct 1 ms 2260 KB Output is correct
28 Correct 1 ms 2260 KB Output is correct
29 Correct 2 ms 2260 KB Output is correct
30 Correct 2 ms 2260 KB Output is correct
31 Correct 1 ms 2260 KB Output is correct
32 Correct 1 ms 2260 KB Output is correct
33 Correct 1 ms 2260 KB Output is correct
34 Correct 2 ms 2260 KB Output is correct
35 Correct 1 ms 2260 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2260 KB Output is correct
2 Correct 1 ms 2260 KB Output is correct
3 Correct 1 ms 2260 KB Output is correct
4 Correct 1 ms 2260 KB Output is correct
5 Correct 2 ms 2260 KB Output is correct
6 Correct 2 ms 2260 KB Output is correct
7 Correct 1 ms 2260 KB Output is correct
8 Correct 2 ms 2260 KB Output is correct
9 Correct 1 ms 2260 KB Output is correct
10 Correct 1 ms 2260 KB Output is correct
11 Correct 1 ms 2260 KB Output is correct
12 Correct 1 ms 2260 KB Output is correct
13 Correct 1 ms 2260 KB Output is correct
14 Correct 1 ms 2260 KB Output is correct
15 Correct 1 ms 2260 KB Output is correct
16 Correct 1 ms 2260 KB Output is correct
17 Correct 1 ms 2260 KB Output is correct
18 Runtime error 4 ms 4472 KB Execution killed with signal 11
19 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2260 KB Output is correct
2 Correct 1 ms 2260 KB Output is correct
3 Correct 1 ms 2260 KB Output is correct
4 Correct 1 ms 2260 KB Output is correct
5 Correct 2 ms 2260 KB Output is correct
6 Correct 2 ms 2260 KB Output is correct
7 Correct 1 ms 2260 KB Output is correct
8 Correct 2 ms 2260 KB Output is correct
9 Correct 1 ms 2260 KB Output is correct
10 Correct 1 ms 2260 KB Output is correct
11 Correct 1 ms 2260 KB Output is correct
12 Correct 1 ms 2260 KB Output is correct
13 Correct 1 ms 2260 KB Output is correct
14 Correct 1 ms 2260 KB Output is correct
15 Correct 1 ms 2260 KB Output is correct
16 Correct 1 ms 2260 KB Output is correct
17 Correct 1 ms 2260 KB Output is correct
18 Correct 1 ms 2260 KB Output is correct
19 Correct 1 ms 2260 KB Output is correct
20 Correct 1 ms 2260 KB Output is correct
21 Correct 1 ms 2292 KB Output is correct
22 Correct 1 ms 2260 KB Output is correct
23 Correct 2 ms 2300 KB Output is correct
24 Correct 2 ms 2304 KB Output is correct
25 Correct 1 ms 2260 KB Output is correct
26 Correct 1 ms 2260 KB Output is correct
27 Correct 1 ms 2260 KB Output is correct
28 Correct 1 ms 2260 KB Output is correct
29 Correct 2 ms 2260 KB Output is correct
30 Correct 2 ms 2260 KB Output is correct
31 Correct 1 ms 2260 KB Output is correct
32 Correct 1 ms 2260 KB Output is correct
33 Correct 1 ms 2260 KB Output is correct
34 Correct 2 ms 2260 KB Output is correct
35 Correct 1 ms 2260 KB Output is correct
36 Runtime error 4 ms 4472 KB Execution killed with signal 11
37 Halted 0 ms 0 KB -