QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#46165#2168. Questsdmga44AC ✓622ms6268kbC++202.1kb2022-08-26 12:36:122022-08-26 12:36:14

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-08-26 12:36:14]
  • 评测
  • 测评结果:AC
  • 用时:622ms
  • 内存:6268kb
  • [2022-08-26 12:36:12]
  • 提交

answer

// #pragma GCC optimize("Ofast,no-stack-protector,unroll-loops", "omit-frame-pointer", "inline")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,fma,tune=native")
// #pragma GCC option("arch=native", "no-zero-upper") // Enable AVX

/// UH Top
#include <bits/stdc++.h>
#define db(x) cerr << #x << ':' << (x) << '\n';
#define all(v) (v).begin(), (v).end()
#define allr(v) (v).rbegin(), (v).rend()
// #define int ll
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
// typedef __int128_t int128;
typedef pair<ll, ll> pii;
typedef pair<ld, ll> pdi;
typedef pair<ld, ld> pdd;
typedef pair<ld, pdd> pdp;
typedef pair<string, ll> psi;
typedef pair<ll, string> pls;
typedef pair<string, string> pss;
typedef pair<ll, pii> pip;
typedef pair<pii, pii> ppp;
typedef complex<ld> point;
typedef vector<point> polygon;
typedef vector<ll> vi;
typedef pair<point, int> ppi;
#define prec(n)        \
    cout.precision(n); \
    cout << fixed
const ll mod = (1e9 + 7);
const ld eps = (1e-9);
const ll oo = (ll)(1e18 + 5);
#define pi acos(-1)
#define MAXN (ll)(4e6 + 5)

bitset<MAXN> dp;

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    // bitset<10> test;
    // for(int i=0;i<10;i++)
    //     test[i]=1;
    // cout << ((test>>3)<<3) << '\n';

    int n,v,c;
    cin >> n >> v >> c;
    vector<pii> ps;
    ll sum=0;
    for(int i=0;i<n;i++)
    {
        int x,d;
        cin >> x >> d;
        ps.push_back(pii(d*v+x*c,x));
        sum+=x;
    }

    sort(all(ps));

    // db("xxx")
    dp[0]=1;
    for(int i=0;i<n;i++)
    {
        int x=ps[i].second;
        int d=(ps[i].first-x*c)/v;

        int lim=min((d*v-1)/c,(int)MAXN-1);
        // cout << lim << ' ' << d << ' ' << x << ' ' << '\n';
        dp=(dp|(((dp<<(MAXN-lim-1))>>(MAXN-lim-1))<<x));
        // cout << dp << '\n';
    }
    // db("xxx")

    int ma=0;
    for(int i=0;i<MAXN;i++)
        if(dp[i])
            ma=i;
    sum+=(ma)*(c-1);
    cout << sum << '\n';

    return 0;   
}

详细

Test #1:

score: 100
Accepted
time: 4ms
memory: 6004kb

input:

3 5 3
2 2
5 5
7 1

output:

38

result:

ok single line: '38'

Test #2:

score: 0
Accepted
time: 10ms
memory: 6196kb

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: 183ms
memory: 6252kb

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: 101ms
memory: 6124kb

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: 6ms
memory: 6104kb

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: 80ms
memory: 6044kb

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: 190ms
memory: 6064kb

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: 561ms
memory: 6176kb

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: 587ms
memory: 6100kb

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: 574ms
memory: 6100kb

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: 606ms
memory: 6252kb

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: 490ms
memory: 6076kb

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: 516ms
memory: 6264kb

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: 347ms
memory: 6200kb

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: 622ms
memory: 6096kb

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: 563ms
memory: 6268kb

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: 4ms
memory: 6028kb

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'