QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#31471#2281. BnPCVingying0#WA 146ms37584kbC++171.1kb2022-05-08 12:29:542022-05-08 12:29:55

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-05-08 12:29:55]
  • 评测
  • 测评结果:WA
  • 用时:146ms
  • 内存:37584kb
  • [2022-05-08 12:29:54]
  • 提交

answer

#include <bits/stdc++.h>
std::map<std::string,int>id;
typedef long long ll;
const int N=1e6+10;
std::vector<int>v[N];
int a[N];
char buf[N];
int main(){
    int n,k;
    scanf("%d%d",&n,&k);
    for(int i=1;i<=n;i++){
        scanf(" %s%d",buf,a+i);
        id[buf]=i;
    }
    int m;
    scanf("%d",&m);
    for(int i=1;i<=m;i++){
        int x;
        scanf(" %s%d",buf,&x);
        v[id[buf]].push_back(x);
    }
    ll ans=0;
    int mxsize=0;
    std::priority_queue<ll>heap;
    for(int i=1;i<=n;i++)if(!v[i].empty()){
        int mx=*std::max_element(v[i].begin(),v[i].end());
        int ct=0;
        if(a[i]<mx){
            k-=mx-a[i];
            a[i]=mx;
        }
        for(int x:v[i])
            if(x<a[i])
                ans+=a[i];
            else
                ct++;
        heap.push(1ll*ct*a[i]+v[i].size());
        mxsize=std::max(mxsize,(int)v[i].size());
    }
    if(k<0){
        puts("-1");
        return 0;
    }
    while(k&&!heap.empty()&&heap.top()>mxsize){
        ans+=heap.top();
        heap.pop();
        k--;
    }
    ans+=1ll*mxsize*k;
    printf("%lld\n",ans);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 7ms
memory: 27128kb

input:

3 14
THISISTHEONE 8
B 0
C 0
8
THISISTHEONE 10
C 0
B 1
B 0
THISISTHEONE 0
C 1
THISISTHEONE 0
THISISTHEONE 0

output:

82

result:

ok single line: '82'

Test #2:

score: 0
Accepted
time: 9ms
memory: 27276kb

input:

3 99
THEFIRSTINCREASE 6
SECONDINCREASE 4
ZZZ 1
9
THEFIRSTINCREASE 4
ZZZ 0
THEFIRSTINCREASE 6
SECONDINCREASE 8
THEFIRSTINCREASE 2
SECONDINCREASE 1
ZZZ 0
SECONDINCREASE 8
THEFIRSTINCREASE 3

output:

429

result:

ok single line: '429'

Test #3:

score: 0
Accepted
time: 19ms
memory: 27272kb

input:

5 20
A 100
B 200
C 300
D 400
E 500
949
A 39
A 23
C 163
A 98
B 36
A 3
A 52
B 152
B 167
B 65
C 142
B 66
B 117
C 288
C 155
E 341
A 97
D 173
E 31
A 62
D 90
E 361
A 42
D 85
E 1
C 141
B 77
B 194
D 221
E 203
D 345
E 48
B 26
D 46
B 74
E 380
B 181
C 243
B 112
A 99
E 403
C 20
E 453
C 149
B 26
E 245
A 74
D 304...

output:

285180

result:

ok single line: '285180'

Test #4:

score: 0
Accepted
time: 7ms
memory: 27280kb

input:

2 1
A 10
B 12
3
A 10
B 10
B 10

output:

35

result:

ok single line: '35'

Test #5:

score: 0
Accepted
time: 4ms
memory: 27136kb

input:

1 1
OVERENTHUSIASTICNESS 41
1
OVERENTHUSIASTICNESS 0

output:

42

result:

ok single line: '42'

Test #6:

score: 0
Accepted
time: 146ms
memory: 37584kb

input:

100000 1000000000
A 1000000000
B 1000000000
C 1000000000
D 1000000000
E 1000000000
F 1000000000
G 1000000000
H 1000000000
I 1000000000
J 1000000000
K 1000000000
L 1000000000
M 1000000000
N 1000000000
O 1000000000
P 1000000000
Q 1000000000
R 1000000000
S 1000000000
T 1000000000
U 1000000000
V 1000000...

output:

100007999593560

result:

ok single line: '100007999593560'

Test #7:

score: 0
Accepted
time: 124ms
memory: 37428kb

input:

100000 1000000000
A 1000000000
B 1000000000
C 1000000000
D 1000000000
E 1000000000
F 1000000000
G 1000000000
H 1000000000
I 1000000000
J 1000000000
K 1000000000
L 1000000000
M 1000000000
N 1000000000
O 1000000000
P 1000000000
Q 1000000000
R 1000000000
S 1000000000
T 1000000000
U 1000000000
V 1000000...

output:

100006999854911

result:

ok single line: '100006999854911'

Test #8:

score: 0
Accepted
time: 16ms
memory: 27248kb

input:

1 1000000000
A 1000000000
100000
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0
A 0...

output:

200000000000000

result:

ok single line: '200000000000000'

Test #9:

score: 0
Accepted
time: 5ms
memory: 27164kb

input:

1 1
A 0
1
A 0

output:

1

result:

ok single line: '1'

Test #10:

score: 0
Accepted
time: 4ms
memory: 27144kb

input:

1 800000
A 0
1000
A 0
A 1
A 2
A 3
A 4
A 5
A 6
A 7
A 8
A 9
A 10
A 11
A 12
A 13
A 14
A 15
A 16
A 17
A 18
A 19
A 20
A 21
A 22
A 23
A 24
A 25
A 26
A 27
A 28
A 29
A 30
A 31
A 32
A 33
A 34
A 35
A 36
A 37
A 38
A 39
A 40
A 41
A 42
A 43
A 44
A 45
A 46
A 47
A 48
A 49
A 50
A 51
A 52
A 53
A 54
A 55
A 56
A 57
A ...

output:

800000000

result:

ok single line: '800000000'

Test #11:

score: 0
Accepted
time: 12ms
memory: 27380kb

input:

2 1000000000
B 235
A 1000000000
100000
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A 1
A...

output:

200000000000000

result:

ok single line: '200000000000000'

Test #12:

score: -100
Wrong Answer
time: 71ms
memory: 32536kb

input:

50457 435832308
A 192207613
B 218291430
C 72712030
D 8339557
E 233611631
F 924985735
G 707429015
H 495523396
I 1524253
J 940348426
K 191972642
L 421286578
M 162847048
N 280111507
O 601044189
P 929639718
Q 893573186
R 920586936
S 56283573
T 46461264
U 4612777
V 221232991
W 968811350
X 783669701
Y 667...

output:

-1

result:

wrong answer 1st lines differ - expected: '0', found: '-1'