oj.uz

Submission #1064539

# Submission time Handle Problem Language Result Execution time Memory
1064539 2024-08-18T14:12:48 Z beaconmc Tricks of the Trade (CEOI23_trade) C++14
0 / 100
 1 ms 604 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;



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

	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];
	ll ans = -1000000000000000;
	FOR(i,0,n){
		set<array<ll,2>> stuff;
		ll sum = 0;
		ll cost = 0;
		FOR(j,i,n){
			cost += price[j];
			sum += sell[j];

			stuff.insert({sell[j], j});
			if (stuff.size() > k){
				auto it = stuff.begin();
				sum -= (*it)[0];
				stuff.erase(it);
			}

			if (stuff.size()==k) ans = max(ans, sum-cost);
		}
	}

	cout << ans << "\n";

	vector<ll> used(n);
	vector<vector<ll>> idk(n+1);

	FOR(i,0,n){
		
		set<array<ll,2>> stuff;
		
		ll sum = 0;
		ll cost = 0;
		FOR(j,i,n){
			cost += price[j];
			sum += sell[j];

			stuff.insert({sell[j], j});

			if (stuff.size() > k){
				auto it = stuff.begin();
				sum -= (*it)[0];
				stuff.erase(it);
			}

			if (stuff.size()==k && (sum-cost) == ans){
				idk[i].push_back((*stuff.begin())[0]);
				idk[j+1].push_back(-(*stuff.begin())[0]);
			}
		}
	}
	multiset<ll> now;
	FOR(i,0,n){
		for (auto&k : idk[i]){
			if (k>0) now.insert(k);
			else now.erase(now.find(k));
		}
		if (sell[i] >= (*now.begin())) used[i] = 1;

	}
	for (auto&i : used) cout << i;







}

Compilation message

trade.cpp: In function 'int main()':
trade.cpp:30:21: warning: comparison of integer expressions of different signedness: 'std::set<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   30 |    if (stuff.size() > k){
      |        ~~~~~~~~~~~~~^~~
trade.cpp:36:20: warning: comparison of integer expressions of different signedness: 'std::set<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   36 |    if (stuff.size()==k) ans = max(ans, sum-cost);
      |        ~~~~~~~~~~~~^~~
trade.cpp:57:21: warning: comparison of integer expressions of different signedness: 'std::set<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   57 |    if (stuff.size() > k){
      |        ~~~~~~~~~~~~~^~~
trade.cpp:63:20: warning: comparison of integer expressions of different signedness: 'std::set<std::array<long long int, 2> >::size_type' {aka 'long unsigned int'} and 'll' {aka 'long long int'} [-Wsign-compare]
   63 |    if (stuff.size()==k && (sum-cost) == ans){
      |        ~~~~~~~~~~~~^~~

Subtask #0
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 348 KB Partially correct
2 Runtime error 0 ms 604 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 344 KB Partially correct
2 Runtime error 0 ms 604 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Partially correct 0 ms 344 KB Partially correct
2 Runtime error 0 ms 604 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #3
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 45.0

# Verdict Execution time Memory Grader output
1 Partially correct 1 ms 348 KB Partially correct
2 Runtime error 0 ms 604 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -