QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#874501 | #8623. Meta | Coffins# | AC ✓ | 10ms | 22244kb | C++17 | 3.3kb | 2025-01-28 09:14:05 | 2025-01-28 09:14:06 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define beg begin
#define All(A) A.beg(),A.end()
#define pb push_back
#define fst first
#define sec second
#define gr greater<>()
#define Lsh(A) sort(All(A)),\
A.erase(unique(All(A)),A.end());
#define u_set unordered_set
#define u_map unordered_map
#define lwb lower_bound
#define upb upper_bound
using ull=unsigned long long;
using ll=long long;
using ld=long double;
using pii=pair<int,int>;
using vi=vector<int>;
using gi=greater<int>;
using str=string;
using bqi=priority_queue<int>;
using lqi=priority_queue<int,vi,gi>;
using qi=queue<int>;
using si=set<int>;
using usi=u_set<int>;
using vll=vector<ll>;
using pll=pair<ll,ll>;
using vvi=vector<vi>;
using vvl=vector<vll>;
using vpi=vector<pii>;
using ply=vll;
const int p=998244353;
const int i2=(p+1)/2;
ll ksm(ll a,ll b)
{
ll ans=1;while(b)
{
if(b&1)ans=ans*a%p;
a=a*a%p;b>>=1;
}return ans;
}const int Msz=1e6+5;
ll fc[Msz],iv[Msz];
void init_C(int n)
{
fc[0]=1;for(int i=1;i<=n;i++)fc[i]=fc[i-1]*i%p;
iv[n]=ksm(fc[n],p-2);for(int i=n-1;i>=0;i--)
iv[i]=iv[i+1]*(i+1)%p;
}ll C(int n,int m)
{
if(n<m||m<0)return 0;
return fc[n]*iv[m]%p*iv[n-m]%p;
}
namespace Poly
{
const int N=1<<21;int rv[N];
const int g=3,ig=(p+1)/g;
void init(int n)
{
for(int i=1;i<=n;i++)
{
rv[i]=rv[i>>1]>>1;
if(i&1)rv[i]|=(n>>1);
}
}
void NTT(ll *a,int l,int o)
{
for(int i=0;i<l;i++)
if(i<rv[i])swap(a[i],a[rv[i]]);
for(int d=1;d<l;d<<=1)
{
ll pw=ksm(g,(p-1)/d/2);
if(o<0)pw=ksm(pw,p-2);
for(int i=0;i<l;i+=(d<<1))
{
ll vl=1;
for(int j=i;j<i+d;j++)
{
ll x=a[j],y=a[j+d]*vl%p;
if((a[j]=x+y)>=p)a[j]-=p;
if((a[j+d]=x-y)<0)a[j+d]+=p;
vl=vl*pw%p;
}
}
}if(o<0)
{
ll vl=ksm(l,p-2);
for(int i=0;i<l;i++)
a[i]=a[i]*vl%p;
}
}
ply mul(ply f,ply g)
{
int n=f.size()-1,m=g.size()-1;
ply rs(n+m+1);int l=1;
while(l<=n+m)l<<=1;
static ll a[N],b[N];init(l);
for(int i=0;i<l;i++)a[i]=b[i]=0;
for(int i=0;i<=n;i++)a[i]=f[i];
for(int i=0;i<=m;i++)b[i]=g[i];
NTT(a,l,1),NTT(b,l,1);
for(int i=0;i<l;i++)a[i]=a[i]*b[i]%p;
NTT(a,l,-1);for(int i=0;i<=n+m;i++)
rs[i]=a[i];return rs;
}
}using Poly::mul;
const int N=305,B=300;
int f[N],g[N],n;
void upd(int &x,int y)
{if(y>x)x=y;}
void solve()
{
memset(f,-1,sizeof(f));cin>>n;
f[0]=0;int ans=0;for(int T=1;T<=n;T++)
{
string s;int x,y,z;
cin>>s>>x>>y>>z;
if(x==-1)x=B+1;
if(y==-1)y=B+1;
if(z==-1)z=B+1;
int t=min({x,y,z});
memset(g,-1,sizeof(g));
for(int i=0;i+t<=B;i++)
g[i+t]=max(f[i+t],f[i]+1);
for(int i=0;i<=B;i++)
f[i]=max(f[i],g[i]),ans=max(ans,f[i]);
}cout<<ans<<'\n';
}void init(){init_C(Msz-5);}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
int t=1;init();//cin>>t;
while(t--)solve();
return 0;
}
这程序好像有点Bug,我给组数据试试?
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 10ms
memory: 20064kb
input:
13 AplusB -1 20 -1 TheBestWife 80 90 60 Cardinality 40 50 30 3D 40 -1 70 EqualStrings 25 15 20 FastTreeQueries 120 -1 40 GeoSharding 25 20 30 HaveYouSeenThisSubarray 80 90 60 InteractiveCasino 50 20 30 JigsawPuzzle 40 50 80 Knapsack -1 40 200 LondonUnderground -1 200 40 Meta 5 7 10
output:
10
result:
ok 1 number(s): "10"
Test #2:
score: 0
Accepted
time: 10ms
memory: 20060kb
input:
10 a 30 30 50 b 30 30 50 c 30 30 50 d 30 30 50 e 30 30 50 f 30 30 50 g 30 30 50 h 30 30 50 i 30 30 50 j 30 30 50
output:
10
result:
ok 1 number(s): "10"
Test #3:
score: 0
Accepted
time: 8ms
memory: 20064kb
input:
11 a 30 30 50 b 30 30 50 c 30 30 50 d 30 30 50 e 30 30 50 f 30 30 50 g 30 30 50 h 30 30 50 i 30 30 50 j 30 30 50 k 30 30 50
output:
10
result:
ok 1 number(s): "10"
Test #4:
score: 0
Accepted
time: 8ms
memory: 20064kb
input:
11 a 31 31 50 b 31 31 50 c 31 31 50 d 31 31 50 e 31 31 50 f 31 31 50 g 31 31 50 h 31 31 50 i 31 31 50 j 31 31 50 k 31 31 50
output:
9
result:
ok 1 number(s): "9"
Test #5:
score: 0
Accepted
time: 8ms
memory: 22108kb
input:
1 a -1 -1 -1
output:
0
result:
ok 1 number(s): "0"
Test #6:
score: 0
Accepted
time: 5ms
memory: 22064kb
input:
1 A 300 300 -1
output:
1
result:
ok 1 number(s): "1"
Test #7:
score: 0
Accepted
time: 9ms
memory: 20192kb
input:
12 A 116 -1 36 B 67 106 -1 C 116 -1 15 D -1 -1 91 E 90 74 13 F -1 -1 -1 G 72 18 -1 H 80 -1 128 I 96 148 -1 J -1 82 111 K 77 -1 103 L 58 148 173
output:
7
result:
ok 1 number(s): "7"
Test #8:
score: 0
Accepted
time: 6ms
memory: 22244kb
input:
8 A 142 148 147 B -1 -1 -1 C -1 -1 -1 D -1 -1 -1 E -1 98 39 F -1 -1 52 G -1 215 -1 H 220 -1 -1
output:
3
result:
ok 1 number(s): "3"
Test #9:
score: 0
Accepted
time: 7ms
memory: 20196kb
input:
4 A 42 -1 37 B -1 -1 15 C -1 36 35 D -1 47 -1
output:
4
result:
ok 1 number(s): "4"
Test #10:
score: 0
Accepted
time: 8ms
memory: 22096kb
input:
14 A -1 21 82 B -1 -1 -1 C 81 197 -1 D -1 -1 -1 E -1 -1 -1 F 208 -1 182 G 212 -1 152 H -1 -1 105 I -1 -1 148 J 6 -1 46 K -1 -1 -1 L 191 -1 -1 M -1 36 51 N 48 -1 34
output:
6
result:
ok 1 number(s): "6"
Test #11:
score: 0
Accepted
time: 7ms
memory: 22116kb
input:
6 A -1 -1 44 B -1 21 2 C -1 21 -1 D 48 33 -1 E 44 -1 -1 F 35 15 9
output:
6
result:
ok 1 number(s): "6"
Test #12:
score: 0
Accepted
time: 8ms
memory: 22072kb
input:
6 A 134 124 22 B 5 28 72 C 77 100 41 D 130 137 96 E 0 150 30 F -1 38 -1
output:
6
result:
ok 1 number(s): "6"
Test #13:
score: 0
Accepted
time: 8ms
memory: 22116kb
input:
12 A 36 22 129 B 30 -1 -1 C -1 169 -1 D 43 -1 175 E -1 106 96 F -1 80 103 G 213 -1 -1 H 130 -1 240 I -1 201 -1 J -1 -1 -1 K -1 -1 101 L 130 129 118
output:
5
result:
ok 1 number(s): "5"
Test #14:
score: 0
Accepted
time: 7ms
memory: 22108kb
input:
4 A 36 -1 29 B 20 -1 49 C 11 -1 77 D -1 76 74
output:
4
result:
ok 1 number(s): "4"
Test #15:
score: 0
Accepted
time: 8ms
memory: 22108kb
input:
14 A -1 68 212 B 207 -1 -1 C -1 -1 217 D -1 -1 204 E -1 79 -1 F 67 101 226 G -1 236 217 H -1 -1 72 I 191 55 149 J -1 150 -1 K 41 51 -1 L 152 -1 -1 M 166 -1 174 N -1 -1 38
output:
5
result:
ok 1 number(s): "5"
Test #16:
score: 0
Accepted
time: 7ms
memory: 22112kb
input:
13 A 27 -1 114 B -1 -1 -1 C 48 -1 210 D 137 169 58 E -1 -1 136 F 154 156 -1 G 102 68 79 H 242 -1 234 I 145 -1 -1 J 190 -1 -1 K 33 246 194 L -1 -1 159 M -1 165 111
output:
5
result:
ok 1 number(s): "5"
Test #17:
score: 0
Accepted
time: 7ms
memory: 22112kb
input:
9 A 71 96 93 B -1 -1 20 C -1 -1 -1 D 41 -1 -1 E 83 -1 3 F -1 -1 14 G -1 35 -1 H -1 -1 -1 I 70 -1 -1
output:
7
result:
ok 1 number(s): "7"
Test #18:
score: 0
Accepted
time: 8ms
memory: 22112kb
input:
1 A 40 -1 81
output:
1
result:
ok 1 number(s): "1"
Test #19:
score: 0
Accepted
time: 8ms
memory: 20064kb
input:
7 A -1 -1 41 B 97 26 -1 C -1 49 92 D -1 69 -1 E 29 44 -1 F -1 -1 54 G 36 -1 50
output:
6
result:
ok 1 number(s): "6"
Test #20:
score: 0
Accepted
time: 8ms
memory: 22236kb
input:
7 A -1 142 53 B 93 54 37 C 95 79 -1 D -1 -1 -1 E -1 76 64 F 43 -1 -1 G -1 143 23
output:
6
result:
ok 1 number(s): "6"
Test #21:
score: 0
Accepted
time: 10ms
memory: 22244kb
input:
13 A -1 -1 76 B 272 -1 -1 C -1 73 148 D -1 224 231 E 143 -1 267 F 26 -1 182 G -1 84 -1 H 209 -1 260 I -1 -1 -1 J -1 182 145 K -1 -1 38 L -1 -1 -1 M 158 132 233
output:
5
result:
ok 1 number(s): "5"
Test #22:
score: 0
Accepted
time: 7ms
memory: 22244kb
input:
9 A 107 66 131 B -1 -1 39 C 113 6 94 D 92 34 119 E -1 -1 30 F 17 -1 -1 G 101 -1 -1 H -1 -1 60 I -1 -1 -1
output:
7
result:
ok 1 number(s): "7"
Test #23:
score: 0
Accepted
time: 8ms
memory: 22244kb
input:
1 A 159 -1 140
output:
1
result:
ok 1 number(s): "1"
Test #24:
score: 0
Accepted
time: 7ms
memory: 22200kb
input:
1 A -1 -1 28
output:
1
result:
ok 1 number(s): "1"
Test #25:
score: 0
Accepted
time: 9ms
memory: 22112kb
input:
7 A -1 148 33 B -1 80 2 C 18 -1 -1 D 87 -1 -1 E 150 88 41 F -1 53 99 G 118 153 81
output:
6
result:
ok 1 number(s): "6"
Test #26:
score: 0
Accepted
time: 7ms
memory: 20068kb
input:
1 A -1 41 -1
output:
1
result:
ok 1 number(s): "1"
Test #27:
score: 0
Accepted
time: 9ms
memory: 22244kb
input:
11 A 1 152 -1 B -1 -1 -1 C -1 -1 50 D 61 -1 29 E 47 10 182 F -1 -1 24 G 134 -1 -1 H 28 99 69 I -1 -1 77 J 140 -1 -1 K -1 46 -1
output:
8
result:
ok 1 number(s): "8"
Test #28:
score: 0
Accepted
time: 8ms
memory: 22224kb
input:
3 A 24 -1 -1 B 2 -1 -1 C 23 -1 -1
output:
3
result:
ok 1 number(s): "3"
Test #29:
score: 0
Accepted
time: 9ms
memory: 22112kb
input:
13 A 61 39 -1 B 109 104 158 C -1 -1 97 D 22 80 -1 E -1 73 -1 F 3 123 -1 G -1 69 30 H -1 84 -1 I -1 124 152 J 92 -1 -1 K -1 -1 -1 L 157 -1 -1 M 86 109 -1
output:
6
result:
ok 1 number(s): "6"
Test #30:
score: 0
Accepted
time: 9ms
memory: 20064kb
input:
10 A -1 -1 -1 B 20 11 -1 C 19 -1 -1 D -1 -1 -1 E 17 -1 -1 F -1 11 27 G 4 -1 10 H -1 26 27 I 29 19 -1 J 28 -1 17
output:
8
result:
ok 1 number(s): "8"
Test #31:
score: 0
Accepted
time: 8ms
memory: 20064kb
input:
2 A -1 71 -1 B -1 43 150
output:
2
result:
ok 1 number(s): "2"
Test #32:
score: 0
Accepted
time: 9ms
memory: 20064kb
input:
12 A -1 -1 -1 B -1 -1 32 C 68 211 93 D -1 -1 85 E 33 -1 64 F -1 111 198 G -1 13 -1 H 177 50 77 I 31 -1 -1 J 36 20 3 K 14 -1 197 L 60 51 31
output:
9
result:
ok 1 number(s): "9"
Test #33:
score: 0
Accepted
time: 9ms
memory: 22112kb
input:
8 A 22 -1 -1 B -1 -1 -1 C -1 21 -1 D -1 11 28 E -1 14 61 F 62 49 -1 G 39 24 -1 H 18 6 60
output:
7
result:
ok 1 number(s): "7"
Test #34:
score: 0
Accepted
time: 7ms
memory: 22016kb
input:
4 A 168 143 -1 B -1 -1 136 C 116 67 105 D 41 10 47
output:
3
result:
ok 1 number(s): "3"
Test #35:
score: 0
Accepted
time: 7ms
memory: 20060kb
input:
10 A -1 -1 -1 B 27 51 -1 C -1 -1 -1 D 27 -1 11 E -1 28 -1 F 34 -1 -1 G -1 -1 43 H -1 16 7 I -1 43 -1 J -1 -1 19
output:
8
result:
ok 1 number(s): "8"
Test #36:
score: 0
Accepted
time: 7ms
memory: 22244kb
input:
12 A -1 30 -1 B -1 108 -1 C -1 70 82 D -1 31 65 E 79 120 -1 F 117 79 14 G -1 -1 31 H 114 -1 -1 I 113 11 -1 J -1 25 85 K -1 44 70 L -1 29 123
output:
9
result:
ok 1 number(s): "9"
Extra Test:
score: 0
Extra Test Passed