QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #559209 | #6355. 5 | Jessica2333 | TL | 31ms | 16136kb | C++14 | 2.0kb | 2024-09-11 20:49:43 | 2024-09-11 20:49:43 |
Judging History
answer
#include<iostream>
#include<vector>
using namespace std;
int N,S,A[200008],buc[400008],W[508],V[508];
struct NODE{
int l,r;
};
vector<NODE> f[400008];
int vis[400008];
const int O=200000;
bool g[2008][2008];
void add_(int p,int l,int r)
{
// cout<<" add_ "<<p-O<<" "<<l<<" "<<r<<"\n";
if(f[p].empty()) f[p].push_back({l,r});
else
{
vector<NODE> vec;
for(auto v:f[p]) vec.push_back(v);
f[p].clear();
bool flag=1;
for(auto v:vec)
{
if(v.r<l-1) f[p].push_back(v);
else if(l<=v.l&&v.r<=r) continue;
else if(v.l>r+1) f[p].push_back({l,r}),f[p].push_back(v),flag=0;
else l=min(l,v.l),r=max(r,v.r);
}
if(flag) f[p].push_back({l,r});
}
}
signed main()
{
cin>>N>>S;
for(int i=1;i<=N;i++) cin>>A[i],buc[A[i]]++;
int N2=0;
// N2=N;
// for(int i=1;i<=N;i++) V[i]=A[i],W[i]=1;
for(int i=1;i<=N;i++)
for(int j=0;buc[A[i]];j++) V[++N2]=A[i]*min(1<<j,buc[A[i]]),W[N2]=min(1<<j,buc[A[i]]),buc[A[i]]-=W[N2];
// g[0][0]=1;
// for(int i=1;i<=N2;i++)
// {
// for(int j=S;j>=0;j--)
// {
// for(int k=0;k<i;k++)
// {
// if(j+V[i]<=S)
// g[j+V[i]][k+1]|=g[j][k];
// }
// }
// }
// int ans0=0;
// for(int i=0;i<=S;i++)
// {
// for(int j=0;j<=N;j++)
// {
// if(g[i][j]) cout<<"g "<<i<<" "<<j<<"\n",ans0++;
// }
// }
// cout<<"ans0:"<<ans0<<"\n";
f[O].push_back({0,0});
for(int i=1;i<=N2;i++)
{
// cout<<"i:"<<i<<"-----\n";
if(V[i]>0)
{
for(int j=S+O-1;j>=0;j--)
{
if(j+V[i]-W[i]>=S+O) continue;
for(auto v:f[j])
{
add_(j+V[i]-W[i],v.l+W[i],v.r+W[i]);
}
}
}
else
{
for(int j=0;j<S+O;j++)
{
if(j+V[i]-W[i]<0) continue;
for(auto v:f[j])
{
add_(j+V[i]-W[i],v.l+W[i],v.r+W[i]);
}
}
}
// for(int j=0;j<=2;j++)
// {
// cout<<"f "<<j<<":\n";
// for(auto v:f[O+j]) cout<<v.l<<" "<<v.r<<";";
// cout<<"\n";
// }
}
long long ans=0;
for(int i=0;i<S+O;i++)
{
for(auto v:f[i])
{
ans+=v.r-v.l+1;
}
}
cout<<ans;
return 0;
}
/*
1 1
0 1
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 5ms
memory: 15800kb
input:
7 9 0 0 0 1 1 2 5
output:
42
result:
ok 1 number(s): "42"
Test #2:
score: 0
Accepted
time: 3ms
memory: 13752kb
input:
10 33 9 9 8 1 1 1 1 1 1 1
output:
48
result:
ok 1 number(s): "48"
Test #3:
score: 0
Accepted
time: 4ms
memory: 15800kb
input:
10 14 2 4 4 1 0 1 0 1 0 1
output:
81
result:
ok 1 number(s): "81"
Test #4:
score: 0
Accepted
time: 4ms
memory: 15872kb
input:
10 14 3 5 3 0 1 0 1 0 1 0
output:
87
result:
ok 1 number(s): "87"
Test #5:
score: 0
Accepted
time: 3ms
memory: 15800kb
input:
40 50 1 1 1 1 3 3 0 3 1 1 0 0 2 1 0 0 1 0 0 2 7 1 2 1 3 0 2 2 3 1 1 0 0 2 0 1 1 0 1 1
output:
1067
result:
ok 1 number(s): "1067"
Test #6:
score: 0
Accepted
time: 9ms
memory: 13788kb
input:
1200 1000 1 1 2 3 0 1 0 0 1 1 0 2 3 0 1 2 0 0 1 0 4 1 1 2 1 1 0 0 1 1 0 1 0 0 1 0 1 0 0 0 1 1 0 1 0 0 1 0 0 1 1 0 1 2 0 4 0 3 1 6 0 1 1 0 0 0 0 4 0 0 0 0 0 0 1 0 0 1 7 1 1 1 0 1 0 1 0 1 1 0 0 1 1 1 3 0 1 0 1 0 0 1 1 2 2 0 1 1 0 0 1 4 1 2 0 0 0 3 0 0 2 1 0 2 0 0 0 1 1 0 0 2 0 0 0 0 1 1 0 1 0 1 6 1 1 ...
output:
737899
result:
ok 1 number(s): "737899"
Test #7:
score: 0
Accepted
time: 31ms
memory: 16136kb
input:
12000 10000 1 1 0 0 1 0 2 1 3 0 0 1 0 3 1 1 0 1 1 1 1 1 2 1 0 1 2 1 0 1 2 0 5 1 1 1 0 2 0 1 0 1 0 3 2 0 1 0 1 1 2 1 0 0 1 1 0 1 0 0 0 1 0 1 0 1 0 4 0 1 3 1 0 0 1 0 1 2 1 0 0 1 1 0 2 1 1 0 1 0 1 0 0 2 1 1 3 0 1 1 1 0 0 0 1 1 1 0 3 0 0 0 2 0 0 0 1 0 2 0 1 1 1 0 0 1 0 1 0 2 0 0 0 0 0 0 0 1 0 1 0 0 4 1 ...
output:
73685347
result:
ok 1 number(s): "73685347"
Test #8:
score: -100
Time Limit Exceeded
input:
36000 30000 0 3 4 1 2 1 1 0 0 1 1 0 1 0 2 1 0 0 0 0 2 1 0 2 0 0 0 0 0 1 1 4 1 4 0 0 2 0 0 0 1 1 0 0 1 1 0 1 0 0 0 0 1 1 0 3 1 1 1 0 0 0 0 0 0 1 2 0 2 3 0 0 0 0 3 1 0 0 0 1 0 1 2 0 0 2 0 1 0 0 2 1 1 0 3 1 6 0 0 1 1 2 0 1 2 0 0 1 0 1 1 0 0 1 0 0 0 1 0 2 0 1 1 1 0 0 5 2 0 5 1 0 0 0 0 1 1 1 8 0 1 1 0 1 ...