oj.uz

Submission #1064596

# Submission time Handle Problem Language Result Execution time Memory
1064596 2024-08-18T15:10:49 Z beaconmc Tricks of the Trade (CEOI23_trade) C++14
45 / 100
 353 ms 457896 KB 
#include <bits/stdc++.h>
 
typedef long long ll;
#define FOR(i,x,y) for(ll i=x; i<y; i++)
#define FORNEG(i,x,y) for(ll i=x; i>y; i--)
 
using namespace std;


ll dp[250005][205];
bool visited[250005][205];

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	FOR(i,0,250005)FOR(j,0,205) dp[i][j] = -100000000000000000, visited[i][j] = 0;

	ll n,k;
	cin >> n >> k;
	vector<ll> price(n), sell(n);
	FOR(i,0,n) cin >> price[i];
	FOR(i,0,n) cin >> sell[i];
	FOR(i,0,n) dp[i][0] = 0;


	FOR(i,0,n){
		FOR(j,0,204){
			dp[i+1][j+1] = max(dp[i][j] + sell[i] - price[i], dp[i][j+1] - price[i]);
		}
	}


	ll ans = -100000000000000000;

	FOR(i,k,n+1){
		ans = max(ans, dp[i][k]);
	}
	FOR(i,k,n+1){
		if (dp[i][k]==ans) visited[i][k] = 1;
	}

	vector<ll> used(n);

	FORNEG(i,n-1,-1){
		FORNEG(j,203,-1){
			if (dp[i+1][j+1] == dp[i][j] + sell[i] - price[i]&& visited[i+1][j+1]){
				visited[i][j] = 1;
				used[i]=1;
			}
			if (dp[i+1][j+1] == dp[i][j+1] - price[i]&& visited[i+1][j+1]){
				visited[i][j+1] = 1;
			}
		}
	}




	cout << ans << endl;
	FOR(i,0,n) cout << used[i];







}

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 451656 KB Output is correct
2 Correct 172 ms 451668 KB Output is correct

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 451696 KB Output is correct
2 Correct 162 ms 451516 KB Output is correct
3 Correct 178 ms 451688 KB Output is correct
4 Correct 152 ms 451668 KB Output is correct
5 Correct 154 ms 451680 KB Output is correct
6 Correct 146 ms 451664 KB Output is correct
7 Correct 151 ms 451664 KB Output is correct
8 Correct 155 ms 451664 KB Output is correct
9 Correct 149 ms 451708 KB Output is correct
10 Correct 157 ms 451668 KB Output is correct
11 Correct 153 ms 451664 KB Output is correct

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 451696 KB Output is correct
2 Correct 162 ms 451516 KB Output is correct
3 Correct 178 ms 451688 KB Output is correct
4 Correct 152 ms 451668 KB Output is correct
5 Correct 154 ms 451680 KB Output is correct
6 Correct 146 ms 451664 KB Output is correct
7 Correct 151 ms 451664 KB Output is correct
8 Correct 155 ms 451664 KB Output is correct
9 Correct 149 ms 451708 KB Output is correct
10 Correct 157 ms 451668 KB Output is correct
11 Correct 153 ms 451664 KB Output is correct
12 Correct 149 ms 451920 KB Output is correct
13 Correct 148 ms 451664 KB Output is correct
14 Correct 146 ms 451668 KB Output is correct
15 Correct 158 ms 451740 KB Output is correct
16 Correct 153 ms 451720 KB Output is correct
17 Correct 151 ms 451664 KB Output is correct
18 Correct 159 ms 451712 KB Output is correct
19 Correct 174 ms 451672 KB Output is correct
20 Correct 153 ms 451660 KB Output is correct
21 Correct 153 ms 451712 KB Output is correct
22 Correct 145 ms 451592 KB Output is correct
23 Incorrect 161 ms 451664 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 146 ms 451664 KB Output is correct
2 Correct 301 ms 457808 KB Output is correct
3 Correct 301 ms 457808 KB Output is correct
4 Correct 340 ms 457808 KB Output is correct
5 Correct 312 ms 457812 KB Output is correct
6 Correct 315 ms 457808 KB Output is correct
7 Correct 323 ms 457864 KB Output is correct
8 Correct 283 ms 457896 KB Output is correct
9 Correct 293 ms 457808 KB Output is correct
10 Correct 281 ms 457812 KB Output is correct

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 451664 KB Output is correct
2 Correct 301 ms 457808 KB Output is correct
3 Correct 301 ms 457808 KB Output is correct
4 Correct 340 ms 457808 KB Output is correct
5 Correct 312 ms 457812 KB Output is correct
6 Correct 315 ms 457808 KB Output is correct
7 Correct 323 ms 457864 KB Output is correct
8 Correct 283 ms 457896 KB Output is correct
9 Correct 293 ms 457808 KB Output is correct
10 Correct 281 ms 457812 KB Output is correct
11 Correct 146 ms 451628 KB Output is correct
12 Correct 282 ms 457804 KB Output is correct
13 Correct 284 ms 457812 KB Output is correct
14 Correct 337 ms 457808 KB Output is correct
15 Correct 323 ms 457832 KB Output is correct
16 Correct 340 ms 457852 KB Output is correct
17 Correct 314 ms 457660 KB Output is correct
18 Correct 289 ms 457808 KB Output is correct
19 Correct 274 ms 457708 KB Output is correct
20 Correct 288 ms 457888 KB Output is correct
21 Correct 157 ms 451664 KB Output is correct
22 Correct 178 ms 451664 KB Output is correct
23 Correct 146 ms 451664 KB Output is correct
24 Correct 152 ms 451628 KB Output is correct
25 Correct 155 ms 451716 KB Output is correct
26 Correct 150 ms 451668 KB Output is correct
27 Correct 155 ms 451664 KB Output is correct
28 Correct 161 ms 451668 KB Output is correct
29 Correct 152 ms 451668 KB Output is correct
30 Correct 152 ms 451668 KB Output is correct
31 Correct 303 ms 457704 KB Output is correct
32 Correct 320 ms 457736 KB Output is correct
33 Correct 353 ms 457812 KB Output is correct
34 Correct 349 ms 457808 KB Output is correct
35 Correct 333 ms 457728 KB Output is correct
36 Correct 309 ms 457812 KB Output is correct
37 Correct 308 ms 457812 KB Output is correct

Subtask #5
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 160 ms 451656 KB Output is correct
2 Correct 172 ms 451668 KB Output is correct
3 Correct 160 ms 451696 KB Output is correct
4 Correct 162 ms 451516 KB Output is correct
5 Correct 178 ms 451688 KB Output is correct
6 Correct 152 ms 451668 KB Output is correct
7 Correct 154 ms 451680 KB Output is correct
8 Correct 146 ms 451664 KB Output is correct
9 Correct 151 ms 451664 KB Output is correct
10 Correct 155 ms 451664 KB Output is correct
11 Correct 149 ms 451708 KB Output is correct
12 Correct 157 ms 451668 KB Output is correct
13 Correct 153 ms 451664 KB Output is correct
14 Correct 149 ms 451920 KB Output is correct
15 Correct 148 ms 451664 KB Output is correct
16 Correct 146 ms 451668 KB Output is correct
17 Correct 158 ms 451740 KB Output is correct
18 Correct 153 ms 451720 KB Output is correct
19 Correct 151 ms 451664 KB Output is correct
20 Correct 159 ms 451712 KB Output is correct
21 Correct 174 ms 451672 KB Output is correct
22 Correct 153 ms 451660 KB Output is correct
23 Correct 153 ms 451712 KB Output is correct
24 Correct 145 ms 451592 KB Output is correct
25 Incorrect 161 ms 451664 KB Output isn't correct
26 Halted 0 ms 0 KB -