QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#619132 | #5303. No Bug No Game | zake | WA | 28ms | 214820kb | C++17 | 1.4kb | 2024-10-07 13:13:46 | 2024-10-07 13:13:46 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
int p[3005],w[3005][3005],ans[3005][3005][2];
void solve()
{
int n,k;
cin>>n>>k;
for(int i=1;i<=n;++i)
{
cin>>p[i];
for(int j=1;j<=p[i];++j) cin>>w[i][j];
if(p[i]>k) p[i]=k;
}
for(int j=1;j<=k;++j)
{
for(int i=1;i<=n;++i)
{
int v=p[i];
if(j-v<0) continue;
ans[j][i][1]=max(ans[j][i][1],ans[j-v][i][0]+w[i][v]);
}
int ma=0,ps=0,ca=0;
for(int i=1;i<=n;++i)
{
if(ans[j][i][1]>ma)
{
ma=ans[j][i][1];
ps=i;
}
}
for(int i=1;i<=n;++i)
{
if(ans[j][i][1]>ca&&i!=ps)
{
ca=ans[j][i][1];
}
}
for(int i=1;i<=n;++i)
{
if(i!=ps)
{
ans[j][i][0]=ma;
}
else ans[j][i][0]=ca;
}
}
for(int v=10;v>=1;v--)
{
for(int i=1;i<=n;++i)
{
if(p[i]<v) continue;
int j=k;
if(ans[j-v][i][0]!=0) ans[j][i][1]=max(ans[j][i][1],ans[j-v][i][0]+w[i][v]);
}
}
int res=0;
// for(int i=1;i<=n;++i)
// {
// for(int j=1;j<=k;++j)
// {
// cout<<ans[j][i][1]<<":"<<ans[j][i][0]<<" ";
// }
// cout<<"\n";
// }
for(int i=1;i<=n;++i)
{
res=max({res,ans[k][i][1],ans[k][i][0]});
}
cout<<res;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int t=1;
//cin>>t;
while(t--) solve();
}
/*
4 4
3 3 4 3
3 3 3 4
3 3 3 4
3 3 3 4
1 3
10 4555 4624 2449 9344 5615 3961 7962 604 6170 100000
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5720kb
input:
4 5 2 1 3 2 1 1 2 3 1 2 1 3
output:
9
result:
ok 1 number(s): "9"
Test #2:
score: -100
Wrong Answer
time: 28ms
memory: 214820kb
input:
3000 3000 10 70562 30723 79371 82224 63977 3362 26909 96449 48163 66159 4 18007 33590 80674 91139 4 10304 31694 70745 50656 10 63090 17226 13187 73881 38137 15237 55750 82751 75854 39658 8 95640 66120 87735 36388 44046 92415 6952 94772 9 60565 27904 98726 87052 35768 25453 14563 34273 92501 10 66332...
output:
299064292
result:
wrong answer 1st numbers differ - expected: '68279788', found: '299064292'