QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#545284 | #836. Farm of Monsters | qwqUwU_ | TL | 1ms | 10088kb | C++14 | 1.1kb | 2024-09-03 08:44:18 | 2024-09-03 08:44:18 |
Judging History
answer
#include<bits/stdc++.h>
#define pb push_back
#define P make_pair
#define fi first
#define se second
#define bit(s,x) (((s)>>(x))&1)
#define pnp(s) __builtin_popcountll(s)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
inline ll read(){
ll x=0,f=1,c=getchar();
while(c<'0'||c>'9')f=(c=='-'?-1:1),c=getchar();
while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
const int N=3e5+3;
int n,A,B,h[N],a[N],b[N];
ll f[N];
int main() {
//freopen("data.in", "r", stdin);
// freopen("myans.out","w",stdout);
n=read(),A=read(),B=read();
rep(i,1,n){
h[i]=read();
int c=(h[i]-1)/B,d=(h[i]-1)%B+1;
a[i]=c+1;
if(A>=B) b[i]=c-1;
else b[i]=c-(d-1)/A-1;
}
rep(i,1,n)f[i]=-1;
f[0]=1;
rep(i,1,n){
static ll g[N];
rep(j,0,i)g[j]=-1;
rep(j,0,i-1)if(~f[j]){
g[j]=max(g[j],f[j]+a[i]);
if(f[j]+b[i]>=0)g[j+1]=max(g[j+1],f[j]+b[i]);
}
rep(j,0,i)f[j]=g[j];
}
per(i,n,0)if(~f[i]){
printf("%d",i);
return 0;
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 10088kb
input:
3 1 1 1 1 1
output:
2
result:
ok answer is '2'
Test #2:
score: 0
Accepted
time: 1ms
memory: 9952kb
input:
3 1 1 2 2 2
output:
3
result:
ok answer is '3'
Test #3:
score: 0
Accepted
time: 0ms
memory: 9896kb
input:
10 34 100 17 27 73 17 60 12 25 53 31 46
output:
5
result:
ok answer is '5'
Test #4:
score: -100
Time Limit Exceeded
input:
300000 1 1 336470888 634074578 642802746 740396295 773386884 579721198 396628655 503722503 971207868 202647942 2087506 268792718 46761498 443917727 16843338 125908043 691952768 717268783 787375312 150414369 693319712 519096230 45277106 856168102 762263554 674936674 407246545 274667941 279198849 5272...