oj.uz

Submission #1071862

# Submission time Handle Problem Language Result Execution time Memory
1071862 2024-08-23T11:57:13 Z Abito Tricks of the Trade (CEOI23_trade) C++17
20 / 100
 496 ms 226656 KB 
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define ppb pop_back
#define ep insert
#define endl '\n'
#define elif else if
#define pow pwr
#define sqrt sqrtt
#define int long long
#define ll long long
typedef unsigned long long ull;
using namespace std;
const int N=6005,K=6005;
int dp[N][K],n,k,a[N],b[N];
bool vis[N][K],ans[N],viss[N][K];
int rec(int i,int j){
	if (j==k) return 0;
	if (j>k) return -1e15;
	if (i>n) return -1e15;
	if (vis[i][j]) return dp[i][j];
	vis[i][j]=1;
	if (j==0) return dp[i][j]=max(rec(i+1,j),rec(i+1,j+1)+b[i]-a[i]);
	return dp[i][j]=max(rec(i+1,j)-a[i],rec(i+1,j+1)+b[i]-a[i]);
}
void getans(){
	queue<pair<int,int>> q;
	q.push({1,0});
	viss[1][0]=1;
	while (!q.empty()){
		int i=q.front().F,j=q.front().S;
		q.pop();
		if (j==k) continue;
		if (j==0){
			if (rec(i+1,j)==dp[i][j] && !viss[i+1][j]){
				q.push({i+1,j});
				viss[i+1][j]=1;
			}
			if (rec(i+1,j+1)+b[i]-a[i]==dp[i][j]){
				ans[i]=1;
				if (!viss[i+1][j+1]){
					q.push({i+1,j+1});
					viss[i+1][j+1]=1;
				}
			}
		}
		else{
			if (rec(i+1,j)-a[i]==dp[i][j] && !viss[i+1][j]){
				q.push({i+1,j});
				viss[i+1][j]=1;
			}
			if (rec(i+1,j+1)+b[i]-a[i]==dp[i][j]){
				ans[i]=1;
				if (!viss[i+1][j+1]){
					q.push({i+1,j+1});
					viss[i+1][j+1]=1;
				}
			}
		}
	}
	return;
}
int32_t main(){
	ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
	cin>>n>>k;
	for (int i=1;i<=n;i++) cin>>a[i];
	for (int i=1;i<=n;i++) cin>>b[i];
	cout<<rec(1,0)<<endl;
	getans();
	for (int i=1;i<=n;i++) cout<<ans[i];cout<<endl;
	return 0;
}

Compilation message

trade.cpp: In function 'int32_t main()':
trade.cpp:71:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   71 |  for (int i=1;i<=n;i++) cout<<ans[i];cout<<endl;
      |  ^~~
trade.cpp:71:38: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   71 |  for (int i=1;i<=n;i++) cout<<ans[i];cout<<endl;
      |                                      ^~~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 2 ms 12108 KB Output is correct
5 Correct 2 ms 12124 KB Output is correct
6 Correct 2 ms 12124 KB Output is correct
7 Correct 2 ms 12292 KB Output is correct
8 Correct 2 ms 12124 KB Output is correct
9 Correct 2 ms 12124 KB Output is correct
10 Correct 2 ms 12124 KB Output is correct
11 Correct 2 ms 12124 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 0 ms 2396 KB Output is correct
4 Correct 2 ms 12108 KB Output is correct
5 Correct 2 ms 12124 KB Output is correct
6 Correct 2 ms 12124 KB Output is correct
7 Correct 2 ms 12292 KB Output is correct
8 Correct 2 ms 12124 KB Output is correct
9 Correct 2 ms 12124 KB Output is correct
10 Correct 2 ms 12124 KB Output is correct
11 Correct 2 ms 12124 KB Output is correct
12 Correct 1 ms 2396 KB Output is correct
13 Correct 1 ms 2396 KB Output is correct
14 Correct 0 ms 2396 KB Output is correct
15 Correct 2 ms 12124 KB Output is correct
16 Correct 2 ms 12124 KB Output is correct
17 Correct 2 ms 12124 KB Output is correct
18 Correct 2 ms 12236 KB Output is correct
19 Correct 2 ms 12124 KB Output is correct
20 Correct 2 ms 12124 KB Output is correct
21 Correct 3 ms 12120 KB Output is correct
22 Correct 2 ms 12124 KB Output is correct
23 Correct 476 ms 226656 KB Output is correct
24 Correct 33 ms 108728 KB Output is correct
25 Correct 196 ms 154408 KB Output is correct
26 Correct 55 ms 113748 KB Output is correct
27 Correct 496 ms 208248 KB Output is correct
28 Correct 22 ms 95580 KB Output is correct
29 Correct 366 ms 208196 KB Output is correct

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2648 KB Output is correct
2 Incorrect 1 ms 2396 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2396 KB Output is correct
2 Correct 0 ms 2396 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 0 ms 2396 KB Output is correct
6 Correct 2 ms 12108 KB Output is correct
7 Correct 2 ms 12124 KB Output is correct
8 Correct 2 ms 12124 KB Output is correct
9 Correct 2 ms 12292 KB Output is correct
10 Correct 2 ms 12124 KB Output is correct
11 Correct 2 ms 12124 KB Output is correct
12 Correct 2 ms 12124 KB Output is correct
13 Correct 2 ms 12124 KB Output is correct
14 Correct 1 ms 2396 KB Output is correct
15 Correct 1 ms 2396 KB Output is correct
16 Correct 0 ms 2396 KB Output is correct
17 Correct 2 ms 12124 KB Output is correct
18 Correct 2 ms 12124 KB Output is correct
19 Correct 2 ms 12124 KB Output is correct
20 Correct 2 ms 12236 KB Output is correct
21 Correct 2 ms 12124 KB Output is correct
22 Correct 2 ms 12124 KB Output is correct
23 Correct 3 ms 12120 KB Output is correct
24 Correct 2 ms 12124 KB Output is correct
25 Correct 476 ms 226656 KB Output is correct
26 Correct 33 ms 108728 KB Output is correct
27 Correct 196 ms 154408 KB Output is correct
28 Correct 55 ms 113748 KB Output is correct
29 Correct 496 ms 208248 KB Output is correct
30 Correct 22 ms 95580 KB Output is correct
31 Correct 366 ms 208196 KB Output is correct
32 Correct 1 ms 2648 KB Output is correct
33 Incorrect 1 ms 2396 KB Output isn't correct
34 Halted 0 ms 0 KB -