NOI.AC
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #197022 | #2384. 进步之星 | snow_trace | 100 | 385ms | 36616kb | C++11 | 2.1kb | 2023-11-05 09:07:24 | 2023-11-05 12:07:26 |
answer
#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
#define lowbit(x) x&(-x)
int n;
int k[3005],a[3005][10];
int dp[3005][3005];
#define endl '\n'
signed main(){
memset(dp,63,sizeof(dp));
cin >>n;
for(int i = 1;i<=n;i++){
cin>>k[i];
for(int j = 1;j<=k[i];j++)cin>>a[i][j];
sort(a[i]+1,a[i]+1+k[i]);
}dp[0][0] = 0;
for(int i = 1;i<=n;i++){
for(int j = 0;j<=i;j++){
if(dp[i-1][j]>10000000)continue;
for(int l = 1;l<=k[i];l++){
if(a[i][l]*(i-1)>dp[i-1][j] or (i == 1 and a[i][l]>0))dp[i][j+1] = min(dp[i][j+1],dp[i-1][j]+a[i][l]);
dp[i][j] = min(dp[i][j],dp[i-1][j]+a[i][l]);
}
}
}for(int i = n;i>=0;i--){
if(dp[n][i]<=10000000){
cout<<i<<endl;return 0;
}
}
return 0;
}
Details
小提示：点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 36496kb
input:
20 2 2426 2325 2 73 2997 2 209 618 2 2130 25 2 1957 2824 2 977 1719 2 1404 2822 2 77 484 2 272 435 2...
output:
14
result:
ok 1 number(s): "14"
Test #2:
score: 10
Accepted
time: 0ms
memory: 36496kb
input:
20 2 1 2400 2 1912 653 2 1814 673 2 585 1287 2 192 693 2 35 1836 2 307 2507 2 659 2728 2 2865 2965 2...
output:
18
result:
ok 1 number(s): "18"
Test #3:
score: 10
Accepted
time: 0ms
memory: 36504kb
input:
100 5 883 2514 2323 2117 2844 5 36 2805 1130 2177 1770 5 2877 1096 441 294 1018 5 392 569 633 2617 1...
output:
95
result:
ok 1 number(s): "95"
Test #4:
score: 10
Accepted
time: 15ms
memory: 36504kb
input:
100 5 459 614 2891 2013 352 5 640 1079 852 31 497 5 2927 55 1416 438 1338 5 1017 1173 2441 1659 119 ...
output:
97
result:
ok 1 number(s): "97"
Test #5:
score: 10
Accepted
time: 3ms
memory: 36504kb
input:
100 5 1634 870 765 1839 44 5 1486 2713 582 2234 457 5 2058 771 2212 811 2958 5 607 478 1503 2016 133...
output:
95
result:
ok 1 number(s): "95"
Test #6:
score: 10
Accepted
time: 73ms
memory: 36612kb
input:
3000 4 1591 2292 2035 2164 4 87 2179 1731 2938 4 1747 2398 912 2288 4 1648 2731 692 496 4 1219 671 7...
output:
2622
result:
ok 1 number(s): "2622"
Test #7:
score: 10
Accepted
time: 65ms
memory: 36616kb
input:
3000 5 1086 1604 674 2160 215 5 1018 2411 913 2294 275 3 570 2572 2665 3 2940 2369 2489 4 1644 2392 ...
output:
2620
result:
ok 1 number(s): "2620"
Test #8:
score: 10
Accepted
time: 79ms
memory: 36616kb
input:
3000 4 1196 476 673 2151 5 302 1379 1979 885 278 4 1841 924 1704 2234 4 2760 208 818 1549 4 2860 157...
output:
2641
result:
ok 1 number(s): "2641"
Test #9:
score: 10
Accepted
time: 73ms
memory: 36616kb
input:
3000 5 857 186 1243 1385 1437 5 2812 330 1826 692 2142 2 2238 654 4 547 1423 1567 30 4 1683 1377 262...
output:
2608
result:
ok 1 number(s): "2608"
Test #10:
score: 10
Accepted
time: 77ms
memory: 36616kb
input:
3000 5 1036 348 85 16 1506 3 2867 2158 100 5 451 2511 472 370 2171 5 297 643 706 650 674 5 2102 563 ...
output:
2624
result:
ok 1 number(s): "2624"
Extra Test:
score: 0
Extra Test Passed
