Submission #1072147

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1072147	2024-08-23T14:56:27 Z	NeroZein	Tricks of the Trade (CEOI23_trade)	C++17	10 / 100	8000 ms	3156 KB

trade

#include <bits/stdc++.h>
using namespace std;

int main() {
	int n, k;
	cin >> n >> k;
	vector<int> c(n), s(n); 
	for (int i = 0; i < n; ++i) {
	  cin >> c[i];
	}
	for (int i = 0; i < n; ++i) {
	  cin >> s[i];
	}
	long long mx = -LLONG_MAX;
	for (int i = 0; i < n; ++i) {
		long long cost = 0; 
		for (int j = i; j < n; ++j) {
			cost -= c[j];
			multiset<int> se; 
			long long biggest = 0; 
			for (int kk = i; kk <= j; ++kk) {
				biggest += s[kk];
				se.insert(s[kk]);
				if ((int) se.size() > k) {
					biggest -= *se.begin();
					se.erase(se.begin());
				}
				if (se.size() == k) {
					mx = max(mx, cost + biggest); 					
				}
			}
		}
	}
	vector<bool> ok(n);
	for (int i = 0; i < n; ++i) {
		long long cost = 0;
		for (int j = i; j < n; ++j) {
			cost -= c[j];
			multiset<int> se; 
			long long biggest = 0; 
			for (int kk = i; kk <= j; ++kk) {
				biggest += s[kk];
				se.insert(s[kk]);
				if ((int) se.size() > k) {
					biggest -= *se.begin();
					se.erase(se.begin());
				}
			}
			if (cost + biggest == mx && se.size() == k) {
				for (int kk = i; kk <= j; ++kk) {
					if (s[kk] >= *se.begin()) {
						ok[kk] = true; 
					}
				}
			}
		}
	}
	cout << mx << '\n';
	for (int i = 0; i < n; ++i) {
	  cout << ok[i];
	}
}

Compilation message

trade.cpp: In function 'int main()':
trade.cpp:28:19: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   28 |     if (se.size() == k) {
      |         ~~~~~~~~~~^~~~
trade.cpp:49:42: warning: comparison of integer expressions of different signedness: 'std::multiset<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |    if (cost + biggest == mx && se.size() == k) {
      |                                ~~~~~~~~~~^~~~

Subtask #0

0.0 / 0.0

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

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	76 ms	424 KB	Output is correct
5	Correct	75 ms	348 KB	Output is correct
6	Correct	59 ms	344 KB	Output is correct
7	Correct	82 ms	348 KB	Output is correct
8	Correct	105 ms	412 KB	Output is correct
9	Correct	77 ms	348 KB	Output is correct
10	Correct	115 ms	348 KB	Output is correct
11	Correct	120 ms	348 KB	Output is correct

Subtask #2

0.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	76 ms	424 KB	Output is correct
5	Correct	75 ms	348 KB	Output is correct
6	Correct	59 ms	344 KB	Output is correct
7	Correct	82 ms	348 KB	Output is correct
8	Correct	105 ms	412 KB	Output is correct
9	Correct	77 ms	348 KB	Output is correct
10	Correct	115 ms	348 KB	Output is correct
11	Correct	120 ms	348 KB	Output is correct
12	Correct	0 ms	432 KB	Output is correct
13	Correct	1 ms	436 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	116 ms	348 KB	Output is correct
16	Correct	80 ms	348 KB	Output is correct
17	Correct	65 ms	348 KB	Output is correct
18	Correct	85 ms	440 KB	Output is correct
19	Correct	98 ms	348 KB	Output is correct
20	Correct	85 ms	348 KB	Output is correct
21	Correct	85 ms	348 KB	Output is correct
22	Correct	88 ms	348 KB	Output is correct
23	Execution timed out	8038 ms	600 KB	Time limit exceeded
24	Halted	0 ms	0 KB	-

Subtask #3

0.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Execution timed out	8079 ms	3156 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #4

0.0 / 25.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Execution timed out	8079 ms	3156 KB	Time limit exceeded
3	Halted	0 ms	0 KB	-

Subtask #5

0.0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	76 ms	424 KB	Output is correct
7	Correct	75 ms	348 KB	Output is correct
8	Correct	59 ms	344 KB	Output is correct
9	Correct	82 ms	348 KB	Output is correct
10	Correct	105 ms	412 KB	Output is correct
11	Correct	77 ms	348 KB	Output is correct
12	Correct	115 ms	348 KB	Output is correct
13	Correct	120 ms	348 KB	Output is correct
14	Correct	0 ms	432 KB	Output is correct
15	Correct	1 ms	436 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	116 ms	348 KB	Output is correct
18	Correct	80 ms	348 KB	Output is correct
19	Correct	65 ms	348 KB	Output is correct
20	Correct	85 ms	440 KB	Output is correct
21	Correct	98 ms	348 KB	Output is correct
22	Correct	85 ms	348 KB	Output is correct
23	Correct	85 ms	348 KB	Output is correct
24	Correct	88 ms	348 KB	Output is correct
25	Execution timed out	8038 ms	600 KB	Time limit exceeded
26	Halted	0 ms	0 KB	-