QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#149637 | #2325. Corns | Neri | AC ✓ | 224ms | 3816kb | C++17 | 1.1kb | 2023-08-25 01:19:48 | 2023-08-25 01:20:05 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define all(x) (x).begin(), (x).end()
#define nall(x) next((x).begin()), (x).end()
constexpr int mod = 1e9 + 7;
constexpr int M = 500;
void slove()
{
int n, W, x;
cin >> n >> W;
unordered_map<int, int> cot;
for(int i = 1;i <= n;++i)
cin >> x, ++cot[x];
// vector<int> f(W + 1);
bitset<200005> f;
f[0] = 1;
int cnt = 0;
for(auto& e : cot)
{
++cnt;
if(cnt >= M)
break;
int tot = e.second;
for(int i = 1;i <= tot; tot -= (i),i <<= 1)
{
for(int j = W;j >= i * e.first;--j)
f[j] = max(f[j], f[j - i * e.first]);
}
for (int i = W; i >= tot * e.first; --i)
f[i] = max(f[i], f[i - tot * e.first]);
}
int ans = -1;
for(int i = 0;i <= W;++i)
if(f[i])
ans = max(ans, i);
cout << ans << endl;
}
signed main()
{
cin.tie(0)->sync_with_stdio(false);
int t = 1;
while(t--)
slove();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3508kb
input:
3 10 1 1 11
output:
2
result:
ok single line: '2'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3596kb
input:
4 10 3 5 3 4
output:
10
result:
ok single line: '10'
Test #3:
score: 0
Accepted
time: 15ms
memory: 3772kb
input:
30669 199323 7 6 7 7 7 7 6 7 7 7 7 6 7 6 6 7 7 7 7 6 6 7 7 7 6 6 6 7 7 7 6 6 7 7 6 6 7 6 7 6 7 6 6 6 6 6 7 7 7 6 6 6 6 6 6 6 7 7 6 6 7 6 6 7 6 6 6 6 6 7 7 7 7 6 7 7 6 6 7 6 7 6 6 6 6 7 6 7 6 7 6 7 6 7 7 7 7 6 7 7 6 6 6 6 7 6 7 7 7 7 6 7 7 7 7 7 7 6 6 6 7 7 7 6 7 7 7 7 6 7 7 6 6 6 6 7 6 7 7 7 6 6 7 7...
output:
199318
result:
ok single line: '199318'
Test #4:
score: 0
Accepted
time: 20ms
memory: 3520kb
input:
22122 199097 9 8 8 10 9 8 10 9 9 9 8 9 8 9 10 8 9 10 10 10 10 10 9 9 10 10 10 10 10 9 8 8 8 10 9 8 9 9 8 10 9 10 10 10 9 8 8 9 10 10 8 9 9 10 9 10 9 9 9 9 9 10 9 8 9 10 9 9 10 10 8 10 8 8 9 10 8 10 10 8 8 9 8 9 8 10 10 10 10 8 8 8 10 9 8 9 8 9 10 9 8 8 10 9 8 10 10 8 9 10 8 10 9 8 10 9 8 9 8 9 9 8 9...
output:
199089
result:
ok single line: '199089'
Test #5:
score: 0
Accepted
time: 20ms
memory: 3628kb
input:
120000 200000 1 2 1 1 1 2 1 2 2 1 1 1 1 1 1 2 1 1 2 2 1 2 1 2 1 1 2 1 2 1 2 2 1 1 1 1 1 2 2 2 2 2 1 1 2 2 2 2 2 1 1 1 1 1 2 2 2 2 1 1 1 2 2 2 1 1 2 1 2 2 1 1 2 2 2 2 2 2 1 2 1 1 2 1 2 1 2 2 1 2 1 1 2 2 1 1 1 1 1 1 2 1 1 2 1 1 1 1 2 2 1 2 1 1 1 1 1 1 1 2 2 1 1 1 1 2 2 2 1 1 2 1 2 1 2 1 2 1 2 2 1 2 1 ...
output:
180055
result:
ok single line: '180055'
Test #6:
score: 0
Accepted
time: 198ms
memory: 3492kb
input:
1243 152688 41 47 45 47 50 37 33 911 42 510 46 33 753 46 47 31 37 50 47 31 39 45 182 48 49 42 40 31 48 807 37 30 38 48 865 43 46 31 42 40 42 46 30 44 31 39 42 45 38 47 47 299 46 598 43 480 40 34 638 37 38 47 210 37 32 38 38 36 50 32 49 494 461 37 34 31 47 42 825 46 44 35 40 225 36 44 231 43 38 40 40...
output:
152688
result:
ok single line: '152688'
Test #7:
score: 0
Accepted
time: 204ms
memory: 3536kb
input:
1241 158399 30 47 914 37 37 31 258 539 31 865 50 47 49 41 107 39 40 704 39 195 30 48 591 557 37 48 32 45 32 31 39 979 42 975 49 32 35 50 38 565 41 34 47 48 30 34 868 993 50 41 50 270 42 535 35 43 36 35 48 72 34 49 45 46 44 48 36 50 48 34 40 972 48 33 730 34 44 30 50 48 35 35 523 668 48 43 48 32 46 3...
output:
158399
result:
ok single line: '158399'
Test #8:
score: 0
Accepted
time: 204ms
memory: 3524kb
input:
1243 157456 31 32 41 37 42 45 42 841 728 46 31 34 43 50 49 48 33 35 39 589 38 39 31 45 754 771 32 687 35 41 46 3 49 37 35 40 36 38 49 733 37 49 849 50 43 34 42 30 31 44 41 39 188 45 194 103 48 33 44 35 36 34 36 44 41 591 40 32 41 36 96 44 49 31 37 46 46 39 37 573 35 63 49 36 34 46 39 46 41 971 38 32...
output:
157456
result:
ok single line: '157456'
Test #9:
score: 0
Accepted
time: 190ms
memory: 3596kb
input:
1244 154207 48 45 36 43 46 49 49 38 871 43 685 38 44 294 38 49 33 35 627 48 564 48 30 32 46 453 43 30 33 46 36 47 440 44 44 37 48 38 34 48 44 37 50 46 37 49 43 115 43 39 419 774 46 45 38 43 35 50 224 832 157 31 34 50 101 46 35 33 49 754 41 39 42 34 49 44 23 626 32 38 39 45 44 33 39 48 48 46 43 46 38...
output:
154207
result:
ok single line: '154207'
Test #10:
score: 0
Accepted
time: 203ms
memory: 3600kb
input:
1244 157697 42 37 159 40 50 31 42 50 899 950 30 41 48 43 37 43 37 36 50 47 41 31 49 35 137 30 144 40 50 38 30 38 38 90 32 49 825 38 32 49 50 31 45 217 40 43 42 43 40 46 42 285 31 977 36 35 34 40 968 47 34 49 39 34 49 270 35 37 60 988 32 35 50 631 33 35 49 521 32 32 33 48 560 803 593 982 49 40 43 41 ...
output:
157697
result:
ok single line: '157697'
Test #11:
score: 0
Accepted
time: 223ms
memory: 3512kb
input:
7060 171395 46 9 7 17 30 48 50 17 7 17 17 18 20 9 31 2 41 17 15 11 11 80 9 3 30 18 3 5 7 7 37 4 17 44 18 14 8 5 1 71 39 19 19 3 20 20 9 17 10 10 34 18 37 10 30 9 43 3 18 8 14 15 37 13 4 19 17 15 11 15 4 11 6 18 5 17 4 13 20 50 14 2 65 5 15 18 5 3 9 9 12 8 4 42 37 62 13 16 10 46 15 17 79 7 14 14 20 3...
output:
171395
result:
ok single line: '171395'
Test #12:
score: 0
Accepted
time: 224ms
memory: 3528kb
input:
7058 172240 99 6 45 20 8 44 12 7 13 18 46 15 14 10 50 37 37 1 12 7 7 3 12 7 13 48 30 6 5 11 68 46 2 20 10 58 3 17 36 7 86 8 57 17 17 4 12 4 59 4 48 37 42 8 7 11 36 5 14 12 15 6 9 74 4 8 19 11 5 19 8 15 20 2 2 4 17 62 16 17 6 14 15 11 50 1 15 14 37 17 4 45 12 8 60 4 46 18 6 18 11 3 19 7 17 35 7 2 52 ...
output:
172240
result:
ok single line: '172240'
Test #13:
score: 0
Accepted
time: 1ms
memory: 3620kb
input:
1 1 1
output:
1
result:
ok single line: '1'
Test #14:
score: 0
Accepted
time: 220ms
memory: 3524kb
input:
7052 171344 3 17 36 19 11 15 34 3 91 17 16 18 93 15 7 1 2 5 7 61 4 6 8 10 3 7 3 2 35 10 82 39 88 4 6 15 40 8 96 17 15 20 98 43 18 11 39 13 58 13 16 49 3 49 15 9 18 10 12 5 10 12 6 3 77 4 71 45 16 3 1 77 2 38 31 13 44 4 13 20 19 10 92 20 17 87 7 64 4 39 81 63 8 52 5 3 6 5 14 2 52 20 4 16 20 13 4 2 13...
output:
171344
result:
ok single line: '171344'
Test #15:
score: 0
Accepted
time: 224ms
memory: 3628kb
input:
7065 171538 8 9 13 92 8 15 4 16 30 12 10 69 68 15 57 16 4 83 5 81 15 67 6 2 40 18 8 9 4 16 19 17 14 16 53 20 7 20 48 91 13 40 14 19 10 13 10 33 88 32 9 100 14 33 64 83 12 78 9 7 9 20 93 8 11 11 11 1 16 8 1 16 9 5 5 17 12 1 5 10 49 14 16 17 8 19 70 35 18 8 17 10 5 5 86 11 19 2 6 48 5 13 12 6 20 20 68...
output:
171538
result:
ok single line: '171538'
Test #16:
score: 0
Accepted
time: 223ms
memory: 3816kb
input:
7063 170730 19 18 3 72 10 19 3 50 5 3 100 2 71 11 6 9 13 52 32 2 69 14 6 2 13 33 13 5 19 4 9 17 1 37 42 40 50 30 19 87 16 12 81 7 20 19 19 17 17 31 12 11 45 46 18 8 2 8 9 34 5 8 74 18 84 46 58 8 15 11 76 17 84 17 7 38 72 11 17 20 20 4 14 5 20 4 5 14 11 13 47 6 1 10 20 85 8 11 7 17 20 13 31 4 10 18 1...
output:
170730
result:
ok single line: '170730'
Test #17:
score: 0
Accepted
time: 224ms
memory: 3548kb
input:
7061 171010 7 5 19 69 15 74 8 18 67 10 18 20 11 16 16 65 13 40 60 38 15 13 12 95 85 42 19 17 5 16 76 1 61 4 9 85 19 1 17 8 15 11 1 13 14 93 6 15 8 16 15 18 7 12 10 15 10 6 1 58 7 6 13 3 20 66 13 8 17 13 11 6 10 10 19 4 7 33 13 11 18 13 18 12 6 57 7 18 9 20 65 7 19 13 14 9 7 18 6 16 1 43 50 7 10 8 12...
output:
171010
result:
ok single line: '171010'
Test #18:
score: 0
Accepted
time: 224ms
memory: 3528kb
input:
7062 171278 97 20 20 68 32 61 10 1 14 1 7 69 42 17 8 7 1 74 18 14 5 2 9 14 47 5 5 13 80 38 2 6 7 31 10 11 33 1 13 11 14 16 9 45 67 6 8 1 11 4 19 78 82 58 65 12 17 98 15 47 19 49 19 11 76 12 11 30 2 60 16 99 12 18 77 2 64 17 71 20 19 3 7 20 3 19 91 18 12 13 31 16 18 30 48 1 75 2 14 16 14 15 6 19 19 1...
output:
171278
result:
ok single line: '171278'
Test #19:
score: 0
Accepted
time: 88ms
memory: 3768kb
input:
32142 191489 6 5 4 7 4 7 11 3 4 4 14 3 13 7 4 3 6 7 4 3 7 6 6 7 5 10 7 5 6 6 7 8 4 4 4 6 12 7 7 5 7 7 5 4 10 5 5 3 7 4 4 15 3 12 3 4 6 6 7 6 7 4 3 7 4 4 3 6 4 10 7 5 5 14 7 7 3 3 5 6 8 3 6 3 5 6 4 7 15 7 7 4 3 4 5 6 7 7 7 11 3 14 3 10 7 4 14 5 7 4 5 5 5 6 6 5 7 7 7 5 11 5 4 13 5 6 6 3 13 3 4 6 5 7 3...
output:
191489
result:
ok single line: '191489'
Test #20:
score: 0
Accepted
time: 89ms
memory: 3596kb
input:
32112 191429 3 6 6 6 6 11 6 3 7 6 6 3 8 4 4 4 3 7 4 7 7 12 7 5 4 7 4 7 5 6 7 3 6 7 12 7 7 4 6 12 5 4 7 5 7 3 5 3 3 5 4 6 7 6 7 5 7 4 5 5 6 4 3 4 5 5 7 6 5 5 13 11 7 4 5 3 4 15 5 5 4 5 5 7 3 3 6 6 11 5 7 12 6 11 7 5 7 4 4 3 4 6 5 7 5 3 5 12 5 6 6 5 3 5 4 6 4 6 3 7 4 7 7 6 6 7 5 7 5 5 10 7 4 4 6 3 4 3...
output:
191429
result:
ok single line: '191429'
Test #21:
score: 0
Accepted
time: 89ms
memory: 3604kb
input:
32107 192846 5 3 7 5 7 3 9 6 3 7 6 7 7 10 4 7 7 6 5 7 7 6 6 12 3 7 7 3 4 13 5 7 5 7 6 6 7 4 6 6 4 5 7 16 5 7 4 4 5 4 4 6 6 10 11 7 7 4 4 7 4 4 5 4 8 6 3 4 5 4 3 3 4 3 3 6 7 6 4 5 12 6 3 11 7 6 7 3 6 7 3 7 6 6 5 7 7 6 6 14 7 12 7 6 3 6 7 6 10 5 3 4 4 3 5 4 7 7 8 7 3 7 6 3 4 5 3 7 4 6 3 3 6 7 5 5 4 4 ...
output:
192846
result:
ok single line: '192846'
Test #22:
score: 0
Accepted
time: 91ms
memory: 3596kb
input:
32136 191995 14 7 3 6 4 4 3 4 3 4 4 14 7 3 3 6 4 5 3 7 6 4 5 4 7 7 4 4 7 3 6 4 8 8 4 7 15 13 4 10 4 7 6 4 7 3 3 6 11 10 6 7 7 5 6 10 4 7 4 5 12 7 7 3 4 6 3 6 3 3 7 4 7 5 3 11 5 7 4 13 7 5 6 6 4 5 5 7 3 4 6 5 4 7 5 3 6 15 4 3 15 4 6 7 5 10 5 7 10 4 5 5 4 5 7 4 4 6 7 3 3 5 5 12 13 3 5 5 7 10 7 5 4 6 7...
output:
191995
result:
ok single line: '191995'
Test #23:
score: 0
Accepted
time: 89ms
memory: 3624kb
input:
32162 192563 6 3 6 4 7 5 4 10 7 7 5 5 3 6 12 5 5 4 6 7 6 5 5 5 5 3 4 5 3 5 13 4 7 5 5 5 4 3 3 4 10 6 3 15 4 3 6 4 5 7 3 5 4 8 5 4 3 11 7 5 7 12 8 10 3 3 5 6 3 3 7 13 7 4 3 3 10 4 3 10 4 5 6 6 3 3 10 6 3 5 4 5 6 4 4 4 7 6 5 3 6 5 5 5 4 4 4 5 3 6 3 6 4 3 5 4 5 3 9 4 8 6 5 13 6 5 5 5 3 5 6 4 4 4 5 4 4 ...
output:
192563
result:
ok single line: '192563'
Test #24:
score: 0
Accepted
time: 1ms
memory: 3480kb
input:
1 1 200000
output:
0
result:
ok single line: '0'
Test #25:
score: 0
Accepted
time: 0ms
memory: 3764kb
input:
3 10 2 3 6
output:
9
result:
ok single line: '9'
Test #26:
score: 0
Accepted
time: 1ms
memory: 3476kb
input:
10 500 1 2 3 4 5 6 400 491 412 492
output:
500
result:
ok single line: '500'
Test #27:
score: 0
Accepted
time: 2ms
memory: 3600kb
input:
2 200000 100000 100000
output:
200000
result:
ok single line: '200000'
Test #28:
score: 0
Accepted
time: 16ms
memory: 3576kb
input:
200000 200000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
200000
result:
ok single line: '200000'
Test #29:
score: 0
Accepted
time: 5ms
memory: 3588kb
input:
100000 100000 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 ...
output:
100000
result:
ok single line: '100000'
Test #30:
score: 0
Accepted
time: 24ms
memory: 3540kb
input:
49900 199570 3 3 3 4 4 5 3 3 5 3 4 5 3 5 5 3 3 3 5 3 3 5 4 4 3 5 3 4 3 5 4 4 3 4 5 5 5 4 3 4 5 4 4 5 4 5 5 4 3 3 5 3 4 4 3 3 3 3 4 5 4 4 5 3 4 4 5 5 3 4 3 4 3 5 3 4 5 3 4 4 3 4 4 4 4 3 5 3 3 5 3 3 3 5 3 4 4 4 5 3 4 4 5 4 5 4 4 4 5 3 5 4 3 5 3 3 5 5 3 3 4 3 4 5 5 4 4 3 4 4 5 3 3 3 3 5 5 4 5 4 3 4 4 3...
output:
199568
result:
ok single line: '199568'