This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (now.size()==0) continue;
if (sell[i] >= (*now.begin())) used[i] = 1;
}
for (auto&i : used) cout << i;
}
Compilation message (stderr)
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){
| ~~~~~~~~~~~~^~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |