QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#627772 | #7646. 优惠购物 | ASnown | 25 | 136ms | 59180kb | C++14 | 2.0kb | 2024-10-10 17:06:13 | 2024-10-10 17:06:13 |
Judging History
answer
#include<bits/stdc++.h>
#define file(F) freopen(#F".in","r",stdin),freopen(#F".out","w",stdout)
#define lowbit(x) ((x)&-(x))
#define ALL(x) (x).begin(),(x).end()
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define popcount(x) (__builtin_popcount((x)))
using namespace std;
using ll=long long;
using uint=uint32_t;
template<typename T>
inline bool Max(T &x,T y) { return std::less<T>()(x,y)&&(x=y,true); }
template<typename T>
inline bool Min(T &x,T y) { return std::less<T>()(y,x)&&(x=y,true); }
template<typename T>
using priority_queue_g = priority_queue<T,vector<T>,greater<T>>;
void Solve();
#define int long long
const int INF = 0x3f3f3f3f;
const int N = 1e6+16;
int n,m,c;
int p[N],q[N];
int f[N];
int x[N];
int s[N];
signed main() {
#ifndef ONLINE_JUDGE
#endif
cin.tie(nullptr)->sync_with_stdio(false);
int T; cin>>T; while(T--)
Solve();
}
void Solve() {
cin>>n>>m>>c;
ll sump=0;
for(int i=1;i<=n;i++) cin>>p[i],sump+=p[i];
for(int i=1;i<=n;i++) cin>>q[i];
ll ans=0;
for(int i=1;i<=n;i++) {
int cnt=min({q[i],p[i]%c,m});
ans+=cnt,q[i]-=cnt,f[i]=m-cnt,m+=p[i]/c-cnt;
}
for(int i=n,mn=INF;i>=1;i--) {
int cnt=min({q[i]/c,f[i]/c,mn/(c+1)});
ans+=cnt*c,s[i+1]=cnt*(c+1),f[i]-=cnt*c;
Min(mn-=cnt*(c+1),f[i]);
x[i]=(cnt==q[i]/c?q[i]%c:c);
}
s[1]=0; for(int i=1;i<=n;i++) s[i]+=s[i-1],f[i]-=s[i];
s[n+1]=INF; for(int i=n;i>=1;i--) s[i]=min(s[i+1],f[i]);
priority_queue_g<pair<int,int>> q;
for(int i=1,sum=0;i<=n;i++) if(x[i]) {
q.emplace(x[i],i),ans+=x[i],sum+=x[i]+1;
bool used=true;
while(sum>s[i+1]||sum>f[i]+used) {
assert(!q.empty());
auto [x,id]=q.top(); q.pop();
int tmp=min(x-1,max(sum-s[i+1],sum-f[i]-used));
if(sum-tmp<=s[i+1]&&sum-tmp<=f[i]+used) {
sum-=tmp,ans-=tmp,q.emplace(x-=tmp,id);
break;
}
sum-=tmp+2,ans-=tmp+1;
used&=id!=i;
}
}
printf("%lld\n",sump-ans);
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 2ms
memory: 11956kb
input:
5 10 9 8 10 5 1 2 10 9 2 9 8 8 5 3 1 1 7 2 2 1 3 0 10 1 5 3 2 6 10 5 10 1 4 8 1 1 2 5 6 2 3 1 3 6 1 10 6 10 5 4 9 5 4 10 8 5 2 4 2 4 2 5 1 1 7 5 0 0 10 5 10 6 2 7 4 3 8 10 5 5 4 1 0 6 3 3 5 4 5 0 0 10 6 12 6 8 7 3 1 4 10 2 9 10 0 3 1 3 1 3 1 0 4 7
output:
51 42 49 48 54
result:
ok 5 lines
Test #2:
score: 5
Accepted
time: 2ms
memory: 11952kb
input:
5 10 8 16 2 4 3 3 10 1 8 7 1 10 2 1 1 2 9 0 2 2 1 0 10 6 5 1 8 7 1 5 1 2 5 5 2 1 6 0 0 4 1 0 0 0 0 10 9 9 10 5 3 1 2 1 9 3 1 10 3 0 2 0 2 1 8 2 1 9 10 4 8 1 4 7 9 2 4 7 9 4 6 1 3 2 4 1 0 4 0 4 2 10 10 7 5 1 6 4 7 5 10 6 2 7 2 0 3 4 5 4 7 4 2 1
output:
41 29 34 47 41
result:
ok 5 lines
Test #3:
score: 5
Accepted
time: 2ms
memory: 11952kb
input:
5 10 2 18 2 7 3 1 2 2 10 3 10 9 1 7 2 0 1 1 8 2 8 8 10 6 17 10 7 9 6 8 2 9 5 5 4 10 1 5 5 3 0 4 1 2 2 10 5 10 1 6 3 8 7 7 7 9 7 4 0 3 2 4 1 0 5 5 4 2 10 2 7 6 2 9 9 3 8 7 8 10 10 1 0 8 3 2 2 0 2 1 2 10 6 12 7 10 8 1 2 4 7 8 3 7 6 10 1 0 0 4 0 8 1 0
output:
47 59 54 64 51
result:
ok 5 lines
Subtask #2:
score: 0
Wrong Answer
Test #4:
score: 0
Wrong Answer
time: 136ms
memory: 59180kb
input:
1 1000000 75424149 4 15519624 393474467 66570532 20552964 884794646 633920424 885627436 891022137 207531470 263467015 853563838 909020263 225156643 843397191 555130236 28501962 70380880 400094075 351542363 118716292 772000502 495729611 777038576 845271464 346378405 179347308 90713310 683636539 92786...
output:
500013649896152
result:
wrong answer 1st lines differ - expected: '400011543086868', found: '500013649896152'
Subtask #3:
score: 10
Accepted
Dependency #1:
100%
Accepted
Test #7:
score: 10
Accepted
time: 2ms
memory: 11956kb
input:
1 500 225 2 0 0 2 1 2 1 4 0 0 0 0 0 2 1 2 0 0 1 0 0 1 1 2 0 2 2 3 1 0 0 2 2 0 1 1 2 1 3 1 3 2 0 0 1 2 0 2 0 0 1 1 0 1 1 1 0 1 0 2 3 0 0 1 3 1 0 2 2 1 1 4 1 1 2 1 1 0 3 2 0 0 0 1 3 0 1 0 1 2 1 0 0 2 1 1 1 2 3 2 2 2 1 1 2 2 0 0 1 1 0 0 1 0 1 1 0 1 3 1 2 0 2 2 1 1 2 0 1 0 4 2 0 0 0 0 1 4 1 0 1 0 1 0 0 ...
output:
231
result:
ok single line: '231'
Test #8:
score: 10
Accepted
time: 2ms
memory: 12008kb
input:
1 500 253 10 1 2 1 1 0 0 1 3 3 1 0 0 0 0 0 0 0 2 1 0 0 2 1 0 0 0 2 0 0 1 2 1 0 2 2 1 1 2 1 0 2 1 0 0 0 1 0 2 2 0 1 0 0 1 0 0 1 1 1 0 1 1 0 1 2 0 1 0 0 1 1 1 0 0 0 1 2 2 1 1 1 0 3 1 0 0 0 1 0 1 1 4 3 1 0 0 0 1 0 1 3 1 1 1 1 4 1 0 0 0 1 1 1 2 2 0 0 3 0 0 1 0 2 2 1 0 2 0 1 0 2 0 0 1 1 0 2 1 0 1 1 1 0 0...
output:
278
result:
ok single line: '278'
Test #9:
score: 10
Accepted
time: 0ms
memory: 12012kb
input:
100 5 3 11 0 1 3 0 1 0 0 0 0 0 5 3 11 0 0 2 2 1 0 0 0 1 1 5 3 10 2 1 0 1 1 2 1 0 0 1 5 3 11 2 2 0 0 1 0 0 0 0 1 5 2 11 0 0 4 0 1 0 0 3 0 1 5 5 10 2 0 0 0 3 1 0 0 0 1 5 5 11 3 1 1 0 0 3 0 1 0 0 5 2 11 0 1 2 0 2 0 1 2 0 0 5 4 10 2 1 1 1 0 0 1 0 1 0 5 4 10 1 1 1 2 0 1 0 1 2 0 5 2 11 2 0 3 0 0 1 0 3 0 0...
output:
5 3 2 4 3 3 1 3 3 1 3 3 4 1 3 3 1 4 3 4 2 5 3 4 4 2 4 2 2 3 4 4 3 3 2 3 0 2 3 4 4 3 3 2 2 4 5 2 4 4 3 3 4 3 4 2 3 3 3 2 4 4 5 2 4 2 4 2 3 4 4 4 4 2 2 1 2 4 1 3 4 3 3 0 3 5 5 2 4 3 2 3 4 3 3 4 2 3 5 3
result:
ok 100 lines
Test #10:
score: 10
Accepted
time: 0ms
memory: 11984kb
input:
50 10 4 11 2 0 0 2 0 0 1 1 4 0 2 0 0 1 0 0 1 1 2 0 10 9 11 0 1 2 0 1 1 1 2 2 0 0 0 2 0 1 0 1 1 2 0 10 4 11 1 2 1 3 0 0 2 0 1 0 1 0 1 3 0 0 0 0 0 0 10 9 10 1 0 1 1 2 1 0 1 2 1 1 0 0 0 2 0 0 1 0 0 10 7 11 0 3 0 2 3 0 0 2 0 0 0 3 0 0 3 0 0 2 0 0 10 9 10 0 1 0 1 1 1 1 2 1 2 0 0 0 0 1 1 1 0 0 0 10 6 11 0...
output:
6 3 6 6 3 7 7 6 2 7 3 6 8 4 6 5 3 5 8 8 6 5 7 8 8 8 4 8 5 4 3 5 7 5 4 8 5 5 7 6 7 6 7 8 8 4 2 4 7 6
result:
ok 50 lines
Subtask #4:
score: 10
Accepted
Dependency #3:
100%
Accepted
Test #11:
score: 10
Accepted
time: 0ms
memory: 12044kb
input:
60 10 17 2 14 8 11 5 9 14 9 9 8 13 12 3 8 5 9 1 0 4 2 10 10 13 2 11 11 10 15 8 12 7 8 8 10 11 6 3 8 2 4 7 8 1 4 10 7 2 18 6 15 6 11 6 12 8 9 9 15 0 9 0 5 6 0 6 4 3 10 4 3 12 8 16 11 9 5 6 9 10 14 0 0 5 7 8 1 6 2 1 5 10 23 3 10 14 11 7 9 7 7 12 17 6 5 8 1 5 5 7 7 1 4 3 10 27 3 13 7 11 12 11 12 10 9 9...
output:
57 60 64 75 60 55 68 67 62 76 76 69 71 61 73 60 54 62 62 67 61 71 75 64 63 73 73 56 65 67 63 40 40 46 57 58 53 64 64 46 42 30 39 46 61 54 55 48 64 51 55 57 57 73 40 63 56 70 55 38
result:
ok 60 lines
Test #12:
score: 10
Accepted
time: 2ms
memory: 11904kb
input:
60 10 4 2 6 14 13 9 5 12 14 12 8 7 2 11 3 3 5 2 11 1 3 2 10 14 3 12 11 5 11 13 12 14 5 9 8 12 9 4 11 2 7 4 4 1 3 10 39 3 8 11 9 17 4 16 7 6 15 7 8 2 9 8 3 12 7 1 2 2 10 4 2 9 15 12 11 10 8 6 7 10 12 9 2 6 3 8 1 3 3 4 0 10 4 2 13 10 9 8 7 6 15 11 15 6 8 3 7 2 2 5 0 0 7 2 10 18 3 12 9 8 8 9 9 11 12 9 ...
output:
68 66 49 70 71 64 71 67 73 69 66 65 66 69 60 66 76 64 68 69 68 67 77 67 60 71 76 67 62 65 52 67 48 73 61 51 48 71 40 60 50 49 60 49 66 52 35 68 52 45 32 69 64 56 48 66 58 67 57 50
result:
ok 60 lines
Test #13:
score: 10
Accepted
time: 2ms
memory: 11964kb
input:
6 1000 129 2 0 1 1 0 3 2 0 0 3 0 0 1 0 1 1 0 0 0 0 3 0 1 2 1 3 1 2 2 1 1 1 0 1 1 0 0 1 1 2 1 2 0 1 0 0 1 1 2 1 1 0 0 1 0 1 0 1 0 0 1 2 1 2 2 0 0 0 0 1 1 1 1 0 0 1 0 3 1 0 1 1 2 2 1 0 1 1 3 0 1 1 2 0 0 1 1 0 1 1 2 2 0 1 0 1 1 1 0 1 1 1 1 1 1 0 0 1 0 1 0 1 0 0 1 2 1 1 2 2 1 0 1 1 0 2 1 0 0 2 0 0 4 1 1...
output:
648 569 721 517 613 515
result:
ok 6 lines
Test #14:
score: 10
Accepted
time: 0ms
memory: 11980kb
input:
1 4000 1097 3 4 0 2 3 1 0 2 3 0 3 2 2 1 0 1 3 3 1 0 3 3 0 0 0 0 1 1 1 3 1 1 3 1 3 0 0 5 2 3 3 2 1 2 3 3 1 2 0 0 0 1 2 2 2 2 3 4 1 0 0 1 1 1 0 0 2 0 2 0 2 0 1 3 2 1 1 3 1 4 1 2 1 1 1 0 3 1 1 1 0 1 1 1 1 0 1 1 1 0 2 2 4 1 1 1 2 3 1 1 0 2 1 1 2 2 0 1 1 1 1 3 2 1 0 2 2 4 3 2 1 2 2 0 0 0 3 0 4 1 3 3 0 1 ...
output:
4106
result:
ok single line: '4106'
Test #15:
score: 10
Accepted
time: 0ms
memory: 12288kb
input:
1 6000 3193 3 0 0 2 0 1 0 1 0 2 0 1 1 1 1 1 2 1 3 0 0 0 0 2 3 0 2 2 1 1 0 0 4 0 0 1 1 0 1 0 2 0 1 3 2 1 1 1 0 1 0 1 2 1 0 0 1 1 1 1 1 2 0 2 0 1 2 2 1 3 0 0 0 1 0 1 0 0 3 0 0 2 1 0 1 1 0 0 1 2 0 3 1 1 3 1 2 1 1 0 1 1 0 0 2 0 2 2 0 1 0 0 0 1 1 2 1 0 0 0 2 1 0 0 0 2 0 0 1 0 0 1 1 1 2 0 0 2 0 1 2 1 4 1 ...
output:
3041
result:
ok single line: '3041'
Test #16:
score: 10
Accepted
time: 2ms
memory: 11956kb
input:
60 100 47 9 0 0 1 0 2 1 3 0 0 0 3 0 2 1 1 0 1 3 3 0 0 0 1 1 0 2 1 0 1 4 2 1 0 0 3 1 2 0 0 0 1 2 0 0 1 1 0 0 1 1 0 0 0 0 1 2 2 1 1 0 2 0 0 0 2 2 1 0 2 1 1 3 0 1 1 2 1 2 3 1 1 0 0 1 0 1 1 0 0 1 0 2 1 1 3 2 1 3 3 0 0 0 1 0 0 0 1 0 0 0 3 0 1 0 1 0 1 2 2 0 0 0 0 1 0 2 1 0 1 4 2 1 0 0 3 0 0 0 0 0 1 0 0 0 ...
output:
53 54 50 72 92 85 55 67 62 49 52 67 61 64 61 52 69 80 49 68 73 54 68 59 54 53 50 93 59 56 76 51 57 49 47 53 54 49 51 48 47 58 47 76 57 92 58 47 55 52 57 47 55 44 48 44 61 85 59 68
result:
ok 60 lines
Subtask #5:
score: 0
Wrong Answer
Dependency #4:
100%
Accepted
Test #17:
score: 10
Accepted
time: 0ms
memory: 12032kb
input:
1 6000 46 2 17 6 8 3 6 10 16 15 4 9 19 8 14 2 1 12 9 15 2 4 10 5 12 2 18 15 1 9 3 5 13 18 18 19 2 14 3 11 5 5 1 11 13 17 16 15 20 2 15 17 2 18 2 10 9 4 10 7 1 13 14 12 16 1 2 15 8 6 4 3 3 9 14 1 1 5 11 14 7 13 17 11 10 3 1 3 1 1 18 1 16 7 6 1 12 2 2 20 12 6 3 13 13 17 14 13 3 3 4 10 20 15 12 1 5 9 8...
output:
41940
result:
ok single line: '41940'
Test #18:
score: 10
Accepted
time: 2ms
memory: 11984kb
input:
1 6000 386343231 9449040 30677995 606166482 64470244 539919722 817757337 20170496 579607834 689795263 524957736 546656764 361028698 391584495 524047482 327296033 847341619 52129032 67870655 834711359 761876501 15964444 70523462 444693929 232328662 142733662 685263085 272541277 836463638 343778726 26...
output:
3030427552190
result:
ok single line: '3030427552190'
Test #19:
score: 10
Accepted
time: 2ms
memory: 12000kb
input:
1 6000 354247996 3443180 213864151 765837831 238626006 567010459 275289808 310410229 677785592 209166281 780779218 306065033 938121977 930688154 667094038 260420500 853609748 415404266 799767690 363380476 161106208 445563730 836493546 888755766 552783946 758932491 350484233 736129127 444800319 78929...
output:
2964681340723
result:
ok single line: '2964681340723'
Test #20:
score: 0
Wrong Answer
time: 0ms
memory: 11948kb
input:
600 10 7 2 4 20 22 27 1 19 4 21 13 5 4 13 2 9 1 7 4 10 9 1 10 18 3 5 28 11 30 18 7 14 4 1 7 4 27 0 6 6 1 8 3 0 0 10 30 2 19 23 6 13 5 24 19 18 9 14 13 14 0 12 5 1 0 15 4 9 10 2 2 7 19 19 6 3 14 25 22 6 20 3 12 7 3 3 5 6 0 2 6 10 9 3 18 1 30 5 18 3 5 23 27 18 17 1 23 4 5 0 5 5 0 12 10 4 3 1 17 28 14 ...
output:
88 83 82 107 108 93 95 79 102 152 140 113 104 101 123 113 80 95 97 94 90 91 140 92 120 125 85 72 99 120 79 123 154 101 129 95 78 93 100 91 107 112 78 127 75 115 119 108 166 99 102 99 113 79 111 109 100 78 113 97 117 89 112 85 64 120 98 128 89 94 79 109 81 111 129 119 101 97 102 68 65 84 83 125 80 12...
result:
wrong answer 301st lines differ - expected: '3278201979', found: '4057103855'
Subtask #6:
score: 0
Wrong Answer
Test #24:
score: 15
Accepted
time: 2ms
memory: 11892kb
input:
600 10 21 2 1434256 1792820 8964100 10756920 6454152 717128 9681228 7529844 7171280 10398356 1075692 1075692 1434256 10039792 358564 717128 717128 5737024 3227076 1792820 10 5 4 5500368 6875460 4125274 687544 5500368 4469049 4125276 2750183 9969416 5156593 4469049 3781503 687546 0 1718865 343773 0 2...
output:
46254742 42284068 28465970 36815342 18797080 16608540 59809954 55963386 98157466 99455211 58990996 4474138 59994584 40677040 117326435 26562075 51644186 94269994 59007134 38720301 55628210 40921356 30237996 20727720 83424160 84045033 66629574 18910773 84890678 72094414 49832625 110722258 1360310 120...
result:
ok 600 lines
Test #25:
score: 0
Wrong Answer
time: 18ms
memory: 12240kb
input:
2000 10 19 8 6876660 3438330 687664 11690316 2062992 2062992 2062992 687666 687666 1375330 6876660 2062998 0 5501328 0 0 0 687666 687666 687666 10 15 3 4087344 17371212 15327539 13283868 16349376 9196524 5109180 16349376 7152852 2043672 4087344 15327540 12262032 0 0 2043672 4087344 7152852 4087344 2...
output:
28194264 79703196 11089764 62810972 41503410 26040944 91781613 70998177 18207816 55013070 7566990 59042320 17974772 28271700 5677866 9725704 1225548 29982198 17802890 343025 45817818 73177656 86443886 15493720 79583772 32225792 56508512 62526146 37987857 105719026 44344500 16914540 65295200 2337432 ...
result:
wrong answer 201st lines differ - expected: '37062424155', found: '43718381912'
Subtask #7:
score: 0
Skipped
Dependency #6:
0%
Subtask #8:
score: 0
Skipped
Dependency #6:
0%
Subtask #9:
score: 0
Skipped
Dependency #2:
0%