QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#56066#4963. Numbers on both SidesasasasWA 2ms3612kbC++2.4kb2022-10-16 19:33:422022-10-16 19:33:43

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-10-16 19:33:43]
  • 评测
  • 测评结果:WA
  • 用时:2ms
  • 内存:3612kb
  • [2022-10-16 19:33:42]
  • 提交

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;
}

详细

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'