QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#91016 | #6130. Plants vs. Zombies | yyyyxh | WA | 170ms | 4220kb | C++17 | 895b | 2023-03-26 17:30:06 | 2023-03-26 17:30:09 |
Judging History
answer
#include <cstdio>
using namespace std;
template<typename T>
T read(){
char c=getchar();T x=0;
while(c<48||c>57) c=getchar();
do x=(x<<1)+(x<<3)+(c^48),c=getchar();
while(c>=48&&c<=57);
return x;
}
typedef long long ll;
const int N=1000003;
int n;ll m;
int a[N];
ll b[N];
bool calc(ll lim){
if(lim==0ll) return 1;
ll res=0;
for(int i=1;i<=n+1;++i) b[i]=0;
for(int i=1;i<=n;++i){
if(i==n&&b[i]>=lim) return res<=m;
b[i]+=a[i];++res;
if(b[i]<lim){
ll t=(lim-b[i]+a[i]-1)/a[i];
b[i]+=t*a[i];
b[i+1]+=(t-1)*a[i];
res+=t+t-1;
if(res>m) return 0;
}
}
return res<=m;
}
int main(){
int tc=read<int>();
while(tc--){
n=read<int>();m=read<ll>();
for(int i=1;i<=n;++i) a[i]=read<int>();
ll l=0,r=1e17;
while(l<r){
ll mid=(l+r)>>1;
if(calc(mid)) l=mid+1;
else r=mid;
}
printf("%lld\n",l-1);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 3496kb
input:
2 4 8 3 2 6 6 3 9 10 10 1
output:
6 4
result:
ok 2 number(s): "6 4"
Test #2:
score: -100
Wrong Answer
time: 170ms
memory: 4220kb
input:
116 4 0 3 2 6 6 4 1 3 2 6 6 10 19 10 2 8 4 2 4 9 3 3 3 4 8 3 9 3 6 2 19 2 10 11 15 3 1 1 4 3 7 10 8 6 7 10 10 14 8 7 1 1 10 9 2 8 10 7 2 13 2 3 10 10 8 1 6 6 9 4 7 1 8 8 7 14 6 7 4 5 3 1 3 11 6 8 1 10 9 7 2 6 6 1 3 9 4 10 6 1 3 8 7 7 10 6 2 10 4 7 2 5 11 9 10 5 9 2 9 1 2 4 8 6 2 8 8 1 6 4 5 7 2 9 8 ...
output:
0 0 4 6 20 3 2 13 1 4 0 4 2 8 0 4 24 3 30 12 0 2 4 0 0 2 8 0 2 6 24 38 2 4 3 0 4 12 9 4 2 8 0 2 0 7 30 3 0 0 16 8 0 32 4 28 8 2 0 0 2 0 2 0 5 2 0 0 0 0 5 0 5 6 28 0 0 24 4 0 2 4 0 0 14 5 6 1 0 6 16 3 9 0 4 0 11 12 6 6 2 6 12 0 850 0 19 148 810 660 120 0 174 7533693 1000000000000 29528096847
result:
wrong answer 8th numbers differ - expected: '14', found: '13'