QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#24501 | #2168. Quests | DaBenZhongXiaSongKuaiDi# | AC ✓ | 461ms | 6212kb | C++14 | 922b | 2022-03-31 10:12:55 | 2022-04-30 05:54:24 |
Judging History
answer
#include <bits/stdc++.h>
#define int long long
using namespace std;
pair<int,int> a[2005];
inline bool cmp(pair<int,int> a,pair<int,int> b)
{
return a.first+a.second<b.first+b.second;
}
bitset <5000005> s;
//int dp[10][5000005];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n,v,c;
cin >> n >> v >> c;
for(int i=1;i<=n;i++)
{
cin >> a[i].first >> a[i].second;
a[i].second=(a[i].second*v-1)/c;
a[i].second=min(a[i].second,4000000ll);
}
sort(a+1,a+n+1,cmp);
s[0]=1;
// dp[0][0]=1;
for(int i=1;i<=n;i++)
{
s|=(s<<5000004-a[i].second)>>5000004-a[i].second-a[i].first;
/* for(int j=0;j<=a[i].second;j++)
dp[i][j+a[i].first]|=dp[i-1][j];
for(int j=0;j<=5000000;j++)
dp[i][j]|=dp[i-1][j];*/
}
int ans=0;
for(int i=0;i<=5000000;i++)
if(s[i]/*dp[n][i]*/) ans=max(ans,i*(c-1));
for(int i=1;i<=n;i++) ans+=a[i].first;
cout << ans;
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 7ms
memory: 6048kb
input:
3 5 3 2 2 5 5 7 1
output:
38
result:
ok single line: '38'
Test #2:
score: 0
Accepted
time: 9ms
memory: 6048kb
input:
12 138 903 1 2000 2 2000 4 2000 8 2000 1 2000 2 2000 4 2000 8 2000 1 2000 2 2000 4 2000 8 2000
output:
40635
result:
ok single line: '40635'
Test #3:
score: 0
Accepted
time: 146ms
memory: 6148kb
input:
599 2 2 402 298 404 297 406 296 408 295 410 294 412 293 414 292 416 291 418 290 420 289 422 288 424 287 426 286 428 285 430 284 432 283 434 282 436 281 438 280 440 279 442 278 444 277 446 276 448 275 450 274 452 273 454 272 456 271 458 270 460 269 462 268 464 267 466 266 468 265 470 264 472 263 474 ...
output:
1018602
result:
ok single line: '1018602'
Test #4:
score: 0
Accepted
time: 88ms
memory: 6060kb
input:
330 2000 2000 1 1000000 2 1000000 4 1000000 8 1000000 16 1000000 32 1000000 64 1000000 128 1000000 256 1000000 512 1000000 1024 1000000 1 1000000 2 1000000 4 1000000 8 1000000 16 1000000 32 1000000 64 1000000 128 1000000 256 1000000 512 1000000 1024 1000000 1 1000000 2 1000000 4 1000000 8 1000000 16...
output:
122820000
result:
ok single line: '122820000'
Test #5:
score: 0
Accepted
time: 15ms
memory: 6032kb
input:
20 3 5 13 3 11 13 12 16 18 12 8 39 16 38 29 27 25 40 13 62 19 58 28 53 46 24 52 14 30 55 56 15 12 98 63 15 33 68 27 90 30 91
output:
877
result:
ok single line: '877'
Test #6:
score: 0
Accepted
time: 65ms
memory: 6192kb
input:
241 726 797 1979 952485 796 438071 926 145882 186 38938 1506 573987 1704 715938 1814 1600 1339 737416 481 883184 236 291074 1303 660045 796 906613 323 817487 143 623998 365 754193 1380 748425 1502 865985 1897 367697 714 685543 1907 350084 1817 628647 1688 327185 1507 462003 1441 741266 1882 544931 1...
output:
198494444
result:
ok single line: '198494444'
Test #7:
score: 0
Accepted
time: 157ms
memory: 6212kb
input:
609 2 2 201 1799 202 1798 203 1797 204 1796 205 1795 206 1794 207 1793 208 1792 209 1791 210 1790 211 1789 212 1788 213 1787 214 1786 215 1785 216 1784 217 1783 218 1782 219 1781 220 1780 221 1779 222 1778 223 1777 224 1776 225 1775 226 1774 227 1773 228 1772 229 1771 230 1770 231 1769 232 1768 233 ...
output:
1259901
result:
ok single line: '1259901'
Test #8:
score: 0
Accepted
time: 434ms
memory: 6112kb
input:
1855 1951 1993 1933 623343 1997 551161 1979 972274 1951 507351 1979 991140 1979 921103 1951 503322 1979 508257 1901 953277 1933 527915 1949 527007 1951 669633 1931 566637 1951 879044 1907 582244 1913 870529 1949 919534 1987 638722 1997 904985 1949 560983 1997 898791 1993 911820 1931 731231 1993 9863...
output:
1957429653
result:
ok single line: '1957429653'
Test #9:
score: 0
Accepted
time: 459ms
memory: 6068kb
input:
2000 2000 2000 2000 1000000 2000 1000000 2000 1000000 2000 1000000 2000 1000000 2000 1000000 2000 1000000 2000 1000000 2000 1000000 2000 1000000 2000 1000000 2000 1000000 2000 1000000 2000 1000000 2000 1000000 2000 1000000 2000 1000000 2000 1000000 2000 1000000 2000 1000000 2000 1000000 2000 1000000...
output:
2003000000
result:
ok single line: '2003000000'
Test #10:
score: 0
Accepted
time: 461ms
memory: 6164kb
input:
1980 1999 1997 1 1000000 2 1000000 4 1000000 8 1000000 16 1000000 32 1000000 64 1000000 128 1000000 256 1000000 512 1000000 1024 1000000 2000 1000000 1 1000000 2 1000000 4 1000000 8 1000000 16 1000000 32 1000000 64 1000000 128 1000000 256 1000000 512 1000000 1024 1000000 2000 1000000 1 1000000 2 100...
output:
1333506735
result:
ok single line: '1333506735'
Test #11:
score: 0
Accepted
time: 456ms
memory: 6020kb
input:
1998 1843 1510 1171 493664 1736 97345 801 129462 1237 204412 1302 557576 415 65733 1950 1192 1161 474486 49 669344 1246 583750 1270 536209 786 560155 1908 125671 1191 946843 421 273090 893 496353 1933 87506 1325 505034 885 490773 1209 611430 212 131811 210 988388 1418 50898 1471 27037 1169 126846 15...
output:
1846305011
result:
ok single line: '1846305011'
Test #12:
score: 0
Accepted
time: 443ms
memory: 5944kb
input:
1775 474 31 117 304008 148 38326 1433 538349 876 501613 1282 93349 1327 525666 272 907118 810 995006 937 702971 1249 571286 1989 358967 380 774800 1735 62664 1620 633158 1984 692575 1827 590138 153 307304 476 392153 1239 193592 931 760956 213 153626 1765 335272 1500 750509 608 960690 1277 58738 583 ...
output:
54489909
result:
ok single line: '54489909'
Test #13:
score: 0
Accepted
time: 456ms
memory: 6084kb
input:
1818 1285 46 1389 209192 1858 490830 546 476806 1235 271014 200 50153 312 403247 14 614316 1325 678103 1578 80187 1761 49061 873 952924 1724 877902 1764 532606 1713 588388 451 171133 296 601504 1047 863720 892 263300 17 426080 1420 486368 1093 390243 1270 379115 165 349491 63 569740 605 589672 28 92...
output:
82074764
result:
ok single line: '82074764'
Test #14:
score: 0
Accepted
time: 259ms
memory: 6048kb
input:
1124 1336 1333 1320 302623 782 797205 66 75102 1060 55011 1142 807756 1556 162511 1007 807645 630 945231 1213 145685 214 370347 6 989289 1245 564575 1 870329 1727 84622 1444 391559 887 497910 1178 221391 575 430477 1592 417150 1925 254040 1494 364351 799 173145 1525 335288 1011 399830 335 437509 451...
output:
1336750642
result:
ok single line: '1336750642'
Test #15:
score: 0
Accepted
time: 460ms
memory: 6068kb
input:
2000 2000 2000 2000 1 2000 1 2000 1 2000 1 2000 1 2000 1 2000 1 2000 1 2000 1 2000 1 2000 1 2000 1 2000 1 2000 1 2000 1 2000 1 2000 1 2000 1 2000 1 2000 1 2000 1 2000 1 2000 1 2000 1 2000 1 2000 1 2000 1 2000 1 2000 1 2000 1 2000 1 2000 1 2000 1 2000 1 2000 1 2000 1 2000 1 2000 1 2000 1 2000 1 2000 ...
output:
7998000
result:
ok single line: '7998000'
Test #16:
score: 0
Accepted
time: 421ms
memory: 6152kb
input:
1797 2 2 402 298 404 297 406 296 408 295 410 294 412 293 414 292 416 291 418 290 420 289 422 288 424 287 426 286 428 285 430 284 432 283 434 282 436 281 438 280 440 279 442 278 444 277 446 276 448 275 450 274 452 273 454 272 456 271 458 270 460 269 462 268 464 267 466 266 468 265 470 264 472 263 474...
output:
3054404
result:
ok single line: '3054404'
Test #17:
score: 0
Accepted
time: 8ms
memory: 6004kb
input:
7 3 2 2 1 3 17 11 15 11 7 14 5 11 20 1 17
output:
93
result:
ok single line: '93'