QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#113145 | #2500. Collecting Stamps 3 | lmeowdn | 0 | 4ms | 36480kb | C++14 | 2.3kb | 2023-06-16 15:22:49 | 2023-06-16 15:22:50 |
Judging History
answer
#include<bits/stdc++.h>
#define fi first
#define se second
#define eb emplace_back
#define mp make_pair
using namespace std;
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef __int128 i128;
template<typename T,typename U>
T ceil(T x, U y) {return (x>0?(x+y-1)/y:x/y);}
template<typename T,typename U>
T floor(T x, U y) {return (x>0?x/y:(x-y+1)/y);}
template<class T,class S>
bool chmax(T &a,const S b) {return (a<b?a=b,1:0);}
template<class T,class S>
bool chmin(T &a,const S b) {return (a>b?a=b,1:0);}
int popcnt(int x) {return __builtin_popcount(x);}
int popcnt(ll x) {return __builtin_popcountll(x);}
int topbit(int x) {return (x==0?-1:31-__builtin_clz(x));}
int topbit(ll x) {return (x==0?-1:63-__builtin_clzll(x));}
int lowbit(int x) {return (x==0?-1:__builtin_ctz(x));}
int lowbit(ll x) {return (x==0?-1:__builtin_ctzll(x));}
#define int long long
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
typedef pair<int,int> pii;
typedef vector<int> vi;
typedef vector<pii> vp;
int read() {
int x=0,w=1; char c=getchar();
while(!isdigit(c)) {if(c=='-') w=-1; c=getchar();}
while(isdigit(c)) {x=x*10+(c-'0'); c=getchar();}
return x*w;
}
const int N=405,inf=0x3f3f3f3f3f3f3f3f;
int n,L,d[N],t[N],f[N][N][N>>1],g[N][N][N>>1],ans;
signed main() {
n=read(), L=read();
rep(i,1,n) d[i]=read();
rep(i,1,n) t[i]=read();
rep(i,1,n) d[i+n]=d[i]+L, t[i+n]=t[i];
rep(l,1,2*n) rep(r,1,2*n) rep(x,0,n) f[l][r][x]=g[l][r][x]=inf;
rep(i,1,n) {
int x=(min(d[i],L-d[i])<=t[i]);
f[i][i][0]=f[i+n][i+n][x]=min(d[i],L-d[i]);
f[i][i][x]=f[i+n][i+n][x]=min(d[i],L-d[i]);
g[i][i][0]=g[i+n][i+n][x]=min(d[i],L-d[i]);
g[i][i][x]=g[i+n][i+n][x]=min(d[i],L-d[i]);
}
rep(len,2,n) {
rep(l,1,2*n-len+1) {
int r=l+len-1;
rep(x,0,n) {
int yl=((f[l+1][r][x]+d[l+1]-d[l])<=t[l]);
chmin(f[l][r][x+yl],f[l+1][r][x]+d[l+1]-d[l]);
int yr=((g[l][r-1][x]+d[r]-d[r-1])<=t[r]);
chmin(g[l][r][x+yr],g[l][r-1][x]+d[r]-d[r-1]);
}
rep(x,0,n) {
chmin(f[l][r][x],g[l][r][x]+d[r]-d[l]);
chmin(g[l][r][x],f[l][r][x]+d[r]-d[l]);
if(f[l][r][x]<inf) chmax(ans,x);
if(g[l][r][x]<inf) chmax(ans,x);
}
}
}
printf("%lld\n",ans);
return 0;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 5
Accepted
time: 3ms
memory: 18016kb
input:
5 180 137 149 164 167 171 18 76 14 55 116
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 3ms
memory: 15956kb
input:
5 198 5 12 18 190 192 16 43 200 33 0
output:
4
result:
ok single line: '4'
Test #3:
score: 0
Accepted
time: 2ms
memory: 28252kb
input:
9 198 3 17 22 33 43 44 48 54 65 0 17 29 32 38 46 45 54 66
output:
5
result:
ok single line: '5'
Test #4:
score: 0
Accepted
time: 4ms
memory: 20148kb
input:
6 171 22 30 46 85 96 149 18 179 19 69 87 96
output:
3
result:
ok single line: '3'
Test #5:
score: 0
Accepted
time: 2ms
memory: 22168kb
input:
7 198 5 8 14 188 191 194 197 7 18 50 69 80 35 8
output:
7
result:
ok single line: '7'
Test #6:
score: 0
Accepted
time: 1ms
memory: 36480kb
input:
12 198 71 72 83 94 108 112 119 140 142 143 166 174 124 119 124 111 91 94 85 48 60 63 40 32
output:
9
result:
ok single line: '9'
Test #7:
score: 0
Accepted
time: 1ms
memory: 26200kb
input:
8 178 32 55 69 99 115 134 152 156 61 109 37 65 76 31 103 0
output:
2
result:
ok single line: '2'
Test #8:
score: 0
Accepted
time: 1ms
memory: 30408kb
input:
10 198 1 2 3 10 14 182 183 190 192 196 0 3 17 46 115 142 79 44 8 1
output:
7
result:
ok single line: '7'
Test #9:
score: 0
Accepted
time: 1ms
memory: 34468kb
input:
12 198 18 23 45 53 54 70 101 103 105 110 118 152 21 24 49 45 61 78 108 111 97 107 122 144
output:
8
result:
ok single line: '8'
Test #10:
score: 0
Accepted
time: 1ms
memory: 7736kb
input:
1 2 1 0
output:
0
result:
ok single line: '0'
Test #11:
score: -5
Wrong Answer
time: 2ms
memory: 7784kb
input:
1 2 1 1
output:
0
result:
wrong answer 1st lines differ - expected: '1', found: '0'
Subtask #2:
score: 0
Skipped
Dependency #1:
0%
Subtask #3:
score: 0
Skipped
Dependency #1:
0%
Subtask #4:
score: 0
Skipped
Dependency #1:
0%