oj.uz

Submission #1071858

# Submission time Handle Problem Language Result Execution time Memory
1071858 2024-08-23T11:56:36 Z Abito Tricks of the Trade (CEOI23_trade) C++17
45 / 100
 2340 ms 527024 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=3e5+5,K=205;
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 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 2 ms 8648 KB Output is correct
9 Correct 2 ms 8536 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8796 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 2 ms 8648 KB Output is correct
9 Correct 2 ms 8536 KB Output is correct
10 Correct 1 ms 8540 KB Output is correct
11 Correct 1 ms 8540 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 2 ms 8540 KB Output is correct
14 Correct 1 ms 8536 KB Output is correct
15 Correct 2 ms 8540 KB Output is correct
16 Correct 2 ms 8660 KB Output is correct
17 Correct 1 ms 8540 KB Output is correct
18 Correct 1 ms 8540 KB Output is correct
19 Correct 1 ms 8536 KB Output is correct
20 Correct 1 ms 8540 KB Output is correct
21 Correct 1 ms 8540 KB Output is correct
22 Correct 1 ms 8536 KB Output is correct
23 Incorrect 15 ms 18520 KB Output isn't correct
24 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 217 ms 525928 KB Output is correct
3 Correct 217 ms 481564 KB Output is correct
4 Correct 234 ms 526676 KB Output is correct
5 Correct 235 ms 526924 KB Output is correct
6 Correct 228 ms 526676 KB Output is correct
7 Correct 231 ms 526456 KB Output is correct
8 Correct 221 ms 513872 KB Output is correct
9 Correct 206 ms 501092 KB Output is correct
10 Correct 236 ms 526300 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 217 ms 525928 KB Output is correct
3 Correct 217 ms 481564 KB Output is correct
4 Correct 234 ms 526676 KB Output is correct
5 Correct 235 ms 526924 KB Output is correct
6 Correct 228 ms 526676 KB Output is correct
7 Correct 231 ms 526456 KB Output is correct
8 Correct 221 ms 513872 KB Output is correct
9 Correct 206 ms 501092 KB Output is correct
10 Correct 236 ms 526300 KB Output is correct
11 Correct 1 ms 8536 KB Output is correct
12 Correct 251 ms 525904 KB Output is correct
13 Correct 192 ms 481604 KB Output is correct
14 Correct 261 ms 526740 KB Output is correct
15 Correct 228 ms 526928 KB Output is correct
16 Correct 278 ms 526712 KB Output is correct
17 Correct 241 ms 526292 KB Output is correct
18 Correct 261 ms 513876 KB Output is correct
19 Correct 202 ms 501192 KB Output is correct
20 Correct 220 ms 526412 KB Output is correct
21 Correct 2 ms 8792 KB Output is correct
22 Correct 1 ms 8540 KB Output is correct
23 Correct 2 ms 8656 KB Output is correct
24 Correct 1 ms 8540 KB Output is correct
25 Correct 1 ms 8656 KB Output is correct
26 Correct 1 ms 8540 KB Output is correct
27 Correct 1 ms 8540 KB Output is correct
28 Correct 1 ms 8540 KB Output is correct
29 Correct 2 ms 8540 KB Output is correct
30 Correct 2 ms 8540 KB Output is correct
31 Correct 1949 ms 524636 KB Output is correct
32 Correct 262 ms 527024 KB Output is correct
33 Correct 2218 ms 526664 KB Output is correct
34 Correct 2340 ms 526656 KB Output is correct
35 Correct 2112 ms 526276 KB Output is correct
36 Correct 2188 ms 526096 KB Output is correct
37 Correct 2275 ms 525092 KB Output is correct

Subtask #5
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 2 ms 8796 KB Output is correct
4 Correct 1 ms 8536 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 1 ms 8540 KB Output is correct
8 Correct 1 ms 8540 KB Output is correct
9 Correct 1 ms 8540 KB Output is correct
10 Correct 2 ms 8648 KB Output is correct
11 Correct 2 ms 8536 KB Output is correct
12 Correct 1 ms 8540 KB Output is correct
13 Correct 1 ms 8540 KB Output is correct
14 Correct 1 ms 8540 KB Output is correct
15 Correct 2 ms 8540 KB Output is correct
16 Correct 1 ms 8536 KB Output is correct
17 Correct 2 ms 8540 KB Output is correct
18 Correct 2 ms 8660 KB Output is correct
19 Correct 1 ms 8540 KB Output is correct
20 Correct 1 ms 8540 KB Output is correct
21 Correct 1 ms 8536 KB Output is correct
22 Correct 1 ms 8540 KB Output is correct
23 Correct 1 ms 8540 KB Output is correct
24 Correct 1 ms 8536 KB Output is correct
25 Incorrect 15 ms 18520 KB Output isn't correct
26 Halted 0 ms 0 KB -