QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#736619 | #7646. 优惠购物 | scallionsong | 35 | 592ms | 290180kb | C++14 | 2.9kb | 2024-11-12 12:04:06 | 2024-11-12 12:04:06 |
Judging History
answer
bool M1;
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ull unsigned long long
#define LL __int128
#define db double
#define LD long double
#define Pii pair<int,int>
#define Pll pair<ll,ll>
#define Pull pair<ull,ull>
#define Pdb pair<db,db>
#define fir first
#define sec second
#define vec vector<int>
#define pb push_back
#define qlr cerr<<"qlr\n"
#define dyh cerr<<"dyh\n"
#define pc(x) __builtin_popcount(x)
#define uni(x,y) uniform_int_distribution<int>(x,y)(rng)
#define unl(x,y) uniform_int_distribution<ll>(x,y)(rng)
#define unr(x,y) uniform_real_distribution<double>(x,y)(rng)
#define F(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define UF(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define look_memory cerr<<'\n'<<abs(&M1-&M2)/1024.0/1024<<'\n'
#define look_time cerr<<'\n'<<clock()*1.0/CLOCKS_PER_SEC<<'\n'
mt19937 rng(time(0)^(*new int));
const ll INF=0x3f3f3f3f3f3f3f3f;
const int Mod=1e9+7;
template<typename T>
inline void inc(T &a,T b){
if(b<0) b+=Mod;
a+=b;
if(a>=Mod) a-=Mod;
}
template<typename T>
inline void dec(T &a,T b){
if(b<0) b+=Mod;
a-=b;
if(a<0) a+=Mod;
}
template<typename T>
inline void muc(T &a,T b){
a=a*b%Mod;
}
template<typename T>
inline bool chkmin(T &a,T b){
if(a<=b) return false;
a=b;
return true;
}
template<typename T>
inline bool chkmax(T &a,T b){
if(a>=b) return false;
a=b;
return true;
}
const int M=6000;
ll T,n,m,K,ans;
ll a[1000010],b[1000010],sum[1000010];
ll f[6010][6010];
bool sit1(){
F(i,1,n) if(a[i]!=b[i]) return 0;
return 1;
}
void solve1(){
ans=0;
sum[n+1]=0;
UF(i,n,1) sum[i]=sum[i+1]+a[i];
F(i,1,n){
if(m>=sum[i]);
else if(m+a[i]/K<sum[i+1]){
ll tmp=min(a[i]%K,m);
ans+=a[i]-tmp,m=m-tmp+a[i]/K;
}
else{
ll L=0,R=a[i],mid;
while(L<=R){
mid=(L+R)>>1;
if(m+mid/K>=sum[i]-mid) R=mid-1;
else L=mid+1;
}
chkmax(L,a[i]-m);
ans+=L,m=sum[i+1];
}
}
cout<<ans<<'\n';
}
void solve2(){
F(i,0,n) F(j,0,M) f[i][j]=INF;
f[0][m]=0;
F(i,1,n){
F(j,0,M){
if(f[i-1][j]==INF) continue;
F(k,0,min((ll)j,b[i])) chkmin(f[i][j-k+(a[i]-k)/K],f[i-1][j]+a[i]-k);
}
}
ans=INF;
F(i,0,M) chkmin(ans,f[n][i]);
cout<<ans<<'\n';
}
void solve(){
cin>>n>>m>>K;
F(i,1,n) cin>>a[i];
F(i,1,n) cin>>b[i];
F(i,1,n) chkmin(b[i],a[i]);
if(sit1()) solve1();
else solve2();
}
bool M2;
int main(){
// freopen("D.in","r",stdin);
// freopen("D1.out","w",stdout);
srand(time(0)^(*new int));
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>T;
while(T--) solve();
look_memory;
look_time;
return 0;
}
/*
g++ D1.cpp -o D1 -std=c++14 -O2&&./D1
6 3
1 1 4 5 1 4
1 1 4 -2
1 4 6 1
2 2 5 5
6 5
1 1 4 5 1 4
2 4 6 3
2 1 6 2
1 1 4 -2
1 4 6 1
2 2 5 5
*/
詳細信息
Subtask #1:
score: 5
Accepted
Test #1:
score: 5
Accepted
time: 0ms
memory: 8548kb
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: 10384kb
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: 1ms
memory: 8524kb
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: 10
Accepted
Test #4:
score: 10
Accepted
time: 124ms
memory: 29396kb
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:
400011543086868
result:
ok single line: '400011543086868'
Test #5:
score: 10
Accepted
time: 123ms
memory: 27876kb
input:
1 1000000 290027657 13 304913277 796843021 516017645 319050677 454050563 311934679 136029540 790505371 382952680 125583971 728245481 902515808 812248168 868676972 790078499 415156440 464267202 582710403 940789661 787826252 967007727 383461878 355142003 38823668 153257857 934717389 686901242 36112867...
output:
464602224908438
result:
ok single line: '464602224908438'
Test #6:
score: 10
Accepted
time: 119ms
memory: 10080kb
input:
100 10000 555225459 12 283175257 921770254 7299205 304241949 267180864 651891533 164511492 581458656 706908893 739975249 933584512 596665557 469159082 990911824 978336498 995722553 404329338 864926421 108033148 939393219 883683355 155563579 13934792 536244919 137715285 306298646 959297422 220012187 ...
output:
4588217379181 4629253346598 4052616322788 4685633463207 4611498546635 3286925309424 4700753892257 4389905037385 4633607365103 4688195153421 4178811594145 4752054242985 4664825925836 4665776689820 3962158296116 4640134664463 3364786516333 4529228891211 4651138496620 4597397577514 3343211719775 377293...
result:
ok 100 lines
Subtask #3:
score: 10
Accepted
Dependency #1:
100%
Accepted
Test #7:
score: 10
Accepted
time: 2ms
memory: 32632kb
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: 4ms
memory: 31664kb
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: 5ms
memory: 12244kb
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: 2ms
memory: 8476kb
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: 2ms
memory: 8552kb
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: 10116kb
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: 52ms
memory: 55056kb
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: 50ms
memory: 196236kb
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: 73ms
memory: 290068kb
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: 33ms
memory: 13640kb
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
Runtime Error
Dependency #4:
100%
Accepted
Test #17:
score: 10
Accepted
time: 592ms
memory: 290180kb
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: 0
Runtime Error
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:
result:
Subtask #6:
score: 0
Wrong Answer
Test #24:
score: 0
Wrong Answer
time: 126ms
memory: 8556kb
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:
4557430888798830399 4557430888798830399 4557430888798830399 4557430888798830399 4557430888798830399 4557430888798830399 4557430888798830399 4557430888798830399 4557430888798830399 4557430888798830399 4557430888798830399 4557430888798830399 4557430888798830399 4557430888798830399 4557430888798830399 ...
result:
wrong answer 1st lines differ - expected: '46254742', found: '4557430888798830399'
Subtask #7:
score: 0
Skipped
Dependency #6:
0%
Subtask #8:
score: 0
Skipped
Dependency #6:
0%
Subtask #9:
score: 0
Skipped
Dependency #2:
100%
Accepted
Dependency #5:
0%