QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#113145#2500. Collecting Stamps 3lmeowdn0 4ms36480kbC++142.3kb2023-06-16 15:22:492023-06-16 15:22:50

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-16 15:22:50]
  • 评测
  • 测评结果:0
  • 用时:4ms
  • 内存:36480kb
  • [2023-06-16 15:22:49]
  • 提交

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%