QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#56066 | #4963. Numbers on both Sides | asasas | WA | 2ms | 3612kb | C++ | 2.4kb | 2022-10-16 19:33:42 | 2022-10-16 19:33:43 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
ll n,k,l;
ll a[100005];
ll b[100005];
ll m_cnt;
map<ll,ll> m;
map<ll,ll> candidates;
ll sum_a;
ll sum_b;
void try_best_candidate(){
if(candidates.size() == 0)return;
ll best_candidate = candidates.rbegin()->first;
// just insert any candidate
if(m_cnt < l){
m_cnt++;
sum_b += best_candidate;
m[best_candidate]++;
candidates[best_candidate]--;
if(candidates[best_candidate] == 0)candidates.erase(best_candidate);
return;
}
// smallest map element (non empty map)
ll smallest = m.begin()->first;
if(best_candidate > smallest){
m[best_candidate]++;
m[smallest]--;
candidates[smallest]++;
candidates[best_candidate]--;
sum_b -= smallest;
sum_b += best_candidate;
if(m[smallest] == 0)m.erase(smallest);
if(candidates[best_candidate] == 0)candidates.erase(best_candidate);
return;
}
}
// g++ -std=c++11 main.cpp -o main && ./main
int main() {
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n;
for(ll i=0;i<n;i++)cin>>a[i];
for(ll i=0;i<n;i++)cin>>b[i];
cin >> k >> l;
// first k elements
for(ll i=0;i<k;i++){
sum_a += a[i];
candidates[b[i]]++;
try_best_candidate();
}
ll ans = sum_a + sum_b;
for(ll i=0;i<k;i++){
int old_pos = k-1-i;
int new_pos = n-1-i;
sum_a -= a[old_pos];
sum_a += a[new_pos];
// remove value from m or candidates
{
// if we even have old value in map
if(m[ b[old_pos] ]){
m[ b[old_pos] ]--;
m_cnt--;
sum_b -= b[old_pos];
if(m[ b[old_pos] ] == 0){
m.erase( b[old_pos] );
}
// if not in value map it is in candidate map
} else {
candidates[ b[old_pos] ]--;
if(candidates[ b[old_pos] ] == 0)candidates.erase( b[old_pos] );
}
}
// add new value
{
candidates[ b[new_pos] ]++;
try_best_candidate();
}
ans = max(ans, sum_a + sum_b);
}
cout << ans << endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3596kb
input:
5 9 7 2 2 9 5 2 2 3 1 2 1
output:
23
result:
ok single line: '23'
Test #2:
score: 0
Accepted
time: 2ms
memory: 3588kb
input:
5 9 7 2 2 9 5 9 2 3 1 2 1
output:
25
result:
ok single line: '25'
Test #3:
score: 0
Accepted
time: 2ms
memory: 3612kb
input:
10 53580627 697780592 429665569 16172712 200486124 435516652 711503384 868083709 616939240 492192996 746044490 57589903 507886672 433841177 918380467 426664522 281530079 729659740 980794901 914640542 8 6
output:
8792267986
result:
ok single line: '8792267986'
Test #4:
score: -100
Wrong Answer
time: 2ms
memory: 3596kb
input:
10 730481488 400954693 128613199 713199560 614447169 248941421 37750895 193920847 657063180 854828707 267000572 122726413 949085528 925195735 688098447 253874115 150107099 260234553 36890874 538579428 3 1
output:
2925226962
result:
wrong answer 1st lines differ - expected: '2780952803', found: '2925226962'