QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#728217 | #4931. Comic Binge | pnlong2706 | WA | 19ms | 46752kb | C++17 | 3.2kb | 2024-11-09 14:47:44 | 2024-11-09 14:47:44 |
Judging History
answer
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ull unsigned long long
#define ld long double
#define for_(n) for(ll i=0; i<n; i++)
#define for__(a,b) for(ll i=a; i<b; i++)
#define _for(i,a,b) for(ll i=a; i<b; i++)
#define mp make_pair
#define fi first
#define se second
#define pb push_back
#define pii pair<int, int>
#define pll pair<long long, long long>
#define el "\n"
#define debug(x) if(enable_debug) cerr << "[debug] " << #x << " : " << x << endl;
#define M_PI 3.14159265358979323846
using namespace __gnu_pbds;
using namespace __gnu_cxx;
using namespace std;
typedef tree<ll,null_type, less_equal<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
const long long MOD=(ll)1e9+7;
const bool enable_debug = true;
template<class T, class P>
ostream& operator<<(ostream& os, const pair<T,P> &a) { os << "{" << a.first << ";" << a.second << "}"; return os; }
template<class T>
ostream& operator<<(ostream& os, const vector<T> &a) { ; for(auto it: a) os << it << " "; ; return os; }
template<class T>
ostream& operator<<(ostream& os, const deque<T> &a) { ; for(auto it: a) os << it << " "; ; return os; }
template<class T>
ostream& operator<<(ostream& os, const set<T> &a) { ; for(auto it: a) os << it << " "; ; return os; }
template<class T>
ostream& operator<<(ostream& os, const multiset<T> &a) { ; for(auto it: a) os << it << " "; ; return os; }
ll gcd(ll a, ll b) { return b==0? a : gcd(b,a%b); }
ll lcm(ll a, ll b) { return a/(gcd(a,b))*b; }
ll pow_mod(ll x, ll y, ll mod) { //mod<3.10^9
ll ans=1;
while(y>0) {
if(y%2==1) ans=ans*x%mod;
y=y>>1;
x=x*x%mod;
}
return ans%mod;
}
void solve(int ith) {
int n;
cin >> n;
vector<int> a(n), b(n);
for_(n) cin >> a[i];
for_(n) cin >> b[i];
vector<vector<int>> dp(n*11, vector<int> (n+1, -1));
int ans = 1e9;
dp[b[0]][0] = b[0] + a[0];
if(n==1) ans = dp[b[0]][0];
for(int i=b[0]+1; i<n*11; i++) {
for(int j=1; j<n; j++) {
if(i-b[j] > 0 && dp[i-b[j]][j-1]!=-1) dp[i][j] = max(dp[i-b[j]][j-1], i) + a[j];
if(j>=2) {
if(i-b[j] > 0 && dp[i-b[j]][j-2]!=-1) dp[i][j] = max(dp[i-b[j]][j-2] + a[j-1], i) + a[j];
}
//cout << i << " " << j << " " << dp[i][j] << el;
}
if(dp[i][n-1]!=-1) ans = min(ans, dp[i][n-1]);
}
cout << ans << el;
}
// PLEASE DO CHECK THE CASE THAT YOU CHANGE THE ORIGINAL VALUE OF SOME VAR AND THEN TRY TO USE THE OLD VALUE OF THAT VAR FOR
// ANOTHER EVALUATION IN THE SAME SCOPE
int main() {
clock_t begin=clock();
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("INP.inp","r",stdin);
freopen("OUT.out", "w", stdout);
#endif
int t = 1;
//cin >> t;
for_(t)
solve(i+1);
cerr << "TIME : " << (double)(clock()-begin)/CLOCKS_PER_SEC << "s.";
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 4004kb
input:
6 3 1 1 1 1 2 1 5 3 3 7 4
output:
13
result:
ok single line: '13'
Test #2:
score: 0
Accepted
time: 0ms
memory: 3936kb
input:
2 2 1 1 1
output:
4
result:
ok single line: '4'
Test #3:
score: 0
Accepted
time: 0ms
memory: 3932kb
input:
1 1 1
output:
2
result:
ok single line: '2'
Test #4:
score: 0
Accepted
time: 1ms
memory: 4500kb
input:
161 146 662 336 441 626 77 362 697 911 248 879 40 435 60 518 62 475 908 185 740 435 899 188 673 716 529 524 305 321 998 4 363 598 471 650 379 6 980 971 175 664 328 294 681 201 64 926 608 310 478 404 284 634 239 891 515 433 368 929 457 593 338 432 971 593 134 355 97 658 344 653 592 822 660 403 398 38...
output:
80587
result:
ok single line: '80587'
Test #5:
score: 0
Accepted
time: 7ms
memory: 27464kb
input:
747 4 609 179 580 613 171 82 687 882 977 720 609 967 329 508 803 301 837 550 416 931 416 521 937 268 723 878 33 372 426 2 94 248 979 319 576 859 644 459 365 445 668 337 572 881 775 946 901 992 405 377 896 967 66 792 686 676 232 245 539 217 774 167 747 923 722 295 483 454 195 494 206 779 536 845 438 ...
output:
375240
result:
ok single line: '375240'
Test #6:
score: 0
Accepted
time: 5ms
memory: 8860kb
input:
354 676 379 988 658 926 360 253 901 720 984 387 31 760 194 126 113 974 43 150 228 700 447 346 837 187 222 391 494 972 930 115 668 34 799 797 551 820 981 486 589 961 46 628 198 591 405 833 602 2 772 197 414 288 711 447 790 124 318 860 980 716 650 771 881 92 556 502 742 120 771 275 909 921 151 773 559...
output:
184280
result:
ok single line: '184280'
Test #7:
score: 0
Accepted
time: 1ms
memory: 4248kb
input:
156 694 378 780 513 491 607 610 145 213 697 477 891 113 224 322 540 285 990 445 645 931 94 182 774 402 508 616 113 947 516 134 756 918 118 82 357 481 83 455 152 210 53 348 227 455 455 866 792 956 687 519 588 871 987 609 464 350 916 195 337 414 427 523 398 45 597 146 933 601 768 226 834 838 793 327 9...
output:
77487
result:
ok single line: '77487'
Test #8:
score: 0
Accepted
time: 12ms
memory: 32092kb
input:
812 357 477 934 524 367 251 927 606 59 303 220 578 843 170 164 160 261 418 372 427 585 269 393 132 269 40 487 26 532 272 963 462 676 727 193 475 762 905 982 36 151 181 163 339 115 578 291 853 696 351 333 268 96 62 630 822 776 380 406 572 667 984 590 2 644 146 422 780 478 806 815 770 588 537 95 979 3...
output:
414612
result:
ok single line: '414612'
Test #9:
score: 0
Accepted
time: 12ms
memory: 24812kb
input:
705 328 774 704 230 336 856 105 491 393 233 552 967 124 923 819 717 498 541 235 368 593 883 794 774 328 768 702 507 428 41 965 559 771 848 357 508 18 742 658 473 198 560 122 47 932 311 1000 899 270 309 302 454 165 570 458 766 866 249 702 73 847 860 229 715 731 772 919 171 282 473 691 456 401 504 291...
output:
353599
result:
ok single line: '353599'
Test #10:
score: 0
Accepted
time: 6ms
memory: 11376kb
input:
429 527 713 657 567 171 120 386 718 780 707 301 116 345 562 205 336 759 459 240 423 271 105 491 159 192 87 230 193 927 853 803 25 269 432 700 801 365 101 426 228 706 728 806 648 264 564 174 172 440 795 252 142 804 135 169 796 327 370 194 313 34 279 584 325 781 341 818 697 689 241 763 326 444 777 115...
output:
206039
result:
ok single line: '206039'
Test #11:
score: 0
Accepted
time: 7ms
memory: 12004kb
input:
443 118 88 629 609 415 117 849 134 285 647 490 861 707 727 546 987 317 245 153 827 541 597 143 755 940 481 540 125 175 811 721 348 104 163 772 534 458 529 133 261 38 750 994 359 275 531 953 546 502 945 504 980 92 690 951 1 733 801 519 889 121 983 176 20 433 860 363 867 559 193 77 839 41 47 512 70 29...
output:
217481
result:
ok single line: '217481'
Test #12:
score: 0
Accepted
time: 1ms
memory: 4084kb
input:
100 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 1 1 1 1 1 ...
output:
101
result:
ok single line: '101'
Test #13:
score: 0
Accepted
time: 1ms
memory: 4096kb
input:
100 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 6 1 10 10 5 1 9 8 6 7 5 5 4 6 10 5 6 7 3 8 6 3 3 9 3 6 2 9 7 10 8 5 4 8 5 6 8 5 1 4 4 6 4 4 6 8 ...
output:
266
result:
ok single line: '266'
Test #14:
score: 0
Accepted
time: 0ms
memory: 3944kb
input:
2 10 1 1 10
output:
12
result:
ok single line: '12'
Test #15:
score: 0
Accepted
time: 1ms
memory: 4060kb
input:
100 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 10 3 5 1 2 9 4 8 6 10 2 9 2 1 10 7 9 3 2 1 3 10 7 3 3 5 1 5 8 10 2 5 4 8 3 3 2 6 2 6 2 1 10 9 8 ...
output:
214
result:
ok single line: '214'
Test #16:
score: 0
Accepted
time: 15ms
memory: 46752kb
input:
1000 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 1 1 1 1 1...
output:
1001
result:
ok single line: '1001'
Test #17:
score: 0
Accepted
time: 17ms
memory: 46708kb
input:
1000 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 1 1 1 1 1...
output:
2250
result:
ok single line: '2250'
Test #18:
score: 0
Accepted
time: 19ms
memory: 46724kb
input:
1000 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 1 1 1 1 1...
output:
2399
result:
ok single line: '2399'
Test #19:
score: 0
Accepted
time: 1ms
memory: 4092kb
input:
100 2 2 8 3 7 6 6 4 1 10 9 2 10 3 7 1 10 6 8 3 7 10 4 4 1 3 1 9 5 4 5 2 4 10 1 1 2 8 2 10 1 2 7 4 1 6 2 4 1 6 8 10 9 3 2 8 7 6 7 10 3 4 6 10 5 10 2 8 10 1 7 3 10 1 2 2 8 4 5 7 10 4 7 5 2 5 1 1 2 9 8 7 1 4 5 6 6 6 9 4 5 2 1 8 3 1 1 2 10 1 7 3 1 8 1 10 3 9 8 6 4 6 6 10 9 6 9 8 5 10 8 1 3 1 2 6 10 1 7 ...
output:
520
result:
ok single line: '520'
Test #20:
score: 0
Accepted
time: 1ms
memory: 4024kb
input:
100 4 9 7 5 5 3 8 5 9 5 5 6 7 5 3 8 7 7 7 2 6 3 2 8 8 5 4 6 4 2 9 2 7 3 1 10 6 8 1 3 7 7 4 7 9 9 8 5 10 3 3 3 2 2 2 10 6 7 4 9 10 9 1 7 8 9 5 2 7 6 6 6 6 1 7 4 6 10 10 5 6 2 10 2 9 2 9 8 9 2 3 9 4 6 9 6 2 4 5 9 1 1 1 2 2 2 1 1 1 1 2 2 2 1 1 2 1 2 1 1 1 1 1 1 2 2 1 1 2 1 2 1 2 2 2 2 2 1 1 2 1 1 1 1 2...
output:
574
result:
ok single line: '574'
Test #21:
score: 0
Accepted
time: 1ms
memory: 4024kb
input:
100 9 6 1 1 1 6 6 1 5 4 10 10 4 10 4 10 9 2 7 6 1 3 1 6 6 2 4 6 8 4 7 5 1 8 1 9 9 6 2 10 6 3 10 10 10 7 9 1 9 2 10 2 1 9 9 8 5 6 1 2 6 7 2 9 1 6 5 7 4 2 9 8 4 10 9 3 1 8 10 10 1 3 3 6 1 8 10 2 1 2 4 4 7 7 4 7 1 4 3 9 10 8 9 8 10 9 10 10 9 9 8 9 10 9 9 10 8 9 9 8 10 9 9 9 9 8 8 8 10 9 10 9 10 9 8 9 9...
output:
556
result:
ok single line: '556'
Test #22:
score: 0
Accepted
time: 1ms
memory: 4028kb
input:
100 8 8 10 10 8 9 10 8 10 9 10 10 10 8 9 10 10 10 9 10 9 9 10 9 8 9 8 8 9 8 9 8 8 8 10 10 10 8 8 9 9 9 8 8 9 8 10 8 9 10 9 8 9 9 9 8 9 9 8 10 8 8 10 8 10 9 10 10 8 10 8 9 10 8 9 10 9 10 9 9 8 8 10 10 8 9 9 8 9 10 8 9 10 9 10 8 10 9 8 8 8 8 10 8 8 10 8 9 9 10 10 8 8 9 8 9 8 10 9 8 9 10 10 10 10 10 10...
output:
905
result:
ok single line: '905'
Test #23:
score: 0
Accepted
time: 1ms
memory: 4268kb
input:
100 9 9 9 10 9 10 9 10 9 10 10 10 9 10 10 10 10 9 10 10 9 9 10 9 10 10 9 9 10 10 9 9 9 9 10 10 10 10 10 10 9 9 9 10 9 9 9 10 10 9 10 10 9 10 10 10 9 10 10 10 9 10 9 9 10 10 9 10 10 9 10 10 9 10 10 10 10 9 10 9 10 10 9 9 10 10 9 10 9 9 10 9 9 9 9 9 10 10 10 9 10 9 10 10 10 10 9 10 10 10 9 10 9 10 10 ...
output:
965
result:
ok single line: '965'
Test #24:
score: 0
Accepted
time: 14ms
memory: 46732kb
input:
1000 6 5 5 1 1 5 7 2 4 2 1 3 8 8 2 5 8 7 3 10 6 7 6 6 2 6 5 7 9 9 10 8 1 7 2 3 7 5 1 5 8 10 6 1 7 9 7 6 6 10 2 7 3 3 5 1 4 7 8 9 7 1 4 3 10 7 7 10 9 5 10 2 2 7 4 2 1 10 2 9 6 1 6 8 5 4 8 1 3 6 5 8 10 3 6 6 7 1 8 3 5 3 5 2 5 9 9 6 4 8 9 3 1 3 3 8 9 3 10 8 3 8 3 1 8 8 4 1 3 8 3 1 4 1 9 6 5 5 2 8 4 3 4...
output:
5477
result:
ok single line: '5477'
Test #25:
score: -100
Wrong Answer
time: 0ms
memory: 3872kb
input:
6 1 2 1 1 1 1 1 2 3 2 2 1
output:
9
result:
wrong answer 1st lines differ - expected: '8', found: '9'