QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#134005 | #4931. Comic Binge | ShG | WA | 2ms | 3656kb | C++14 | 2.1kb | 2023-08-02 20:22:34 | 2023-08-02 20:22:36 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
#define rep(a, b, c) for(int (a)=(b);(a)<=(c);(a)++)
#define per(a, b, c) for(int (a)=(b);(a)>=(c);(a)--)
#define mset(var, val) memset(var,val,sizeof(var))
#define ll long long
#define int ll
#define fi first
#define se second
#define no "NO\n"
#define yes "YES\n"
#define pb push_back
#define endl "\n"
#define pii pair<int,int>
#define pll pair<ll,ll>
#define dbg(x...) do{cout<<#x<<" -> ";err(x);}while (0)
void err() { cout << '\n'; }
template<class T, class... Ts>
void err(T arg, Ts... args) {
cout << arg << ' ';
err(args...);
}
const int N = 1000 + 5;
const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const int P = 1e9 + 7;
const double eps = 1e-8;
const double pi = acos(-1.0);
int suf[N],a[N],b[N],aa[N],bb[N],c[N];
pii dp[N];//fi val;se shengyu
void solve() {
int n;
cin>>n;
rep(i,1,n){
cin>>a[i];
}
rep(i,1,n){
cin>>b[i];
}
int sum=b[1];
aa[1]=b[1];
bb[1]=b[1]+a[1];
rep(i,2,n){
sum+=b[i];
aa[i]=max(bb[i-1],sum);
bb[i]=aa[i]+a[i];
}
suf[0]=suf[n+1]=0;
per(i,n,1){
suf[i]=suf[i+1]+(aa[i]-bb[i-1]);
}
suf[1]=0;
rep(i,1,n) {
c[i] = min(b[i], suf[i]);
}
c[1]=0;
dp[n].fi=min(suf[n],c[n]),dp[n].se=max(0ll,suf[n]-c[n]);
per(i,n-1,1){
int mx=0;
dp[i].fi=min(suf[i],c[i]),dp[i].se=max(0ll,suf[i]-c[i]);
if(dp[i+1].fi>dp[i].fi){
dp[i].fi=dp[i+1].fi,dp[i].se=dp[i+1].se;
}
per(j,n,i+2){
if(dp[i].fi<=dp[j].fi+min(dp[j].se+suf[i]-suf[j],c[i])){
dp[i].fi=dp[j].fi+min(dp[j].se+suf[i]-suf[j],c[i]);
dp[i].se=max(0ll,dp[j].se+suf[i]-suf[j]-c[i]);
}
}
// dbg(i,dp[i].fi);
}
cout<<bb[n]-dp[1].fi<<endl;
}
signed main() {
IOS;
int T = 1;
// cin >> T;
while (T--) {
solve();
}
return 0;
}
/*
4
1 1 1 1
6 4 4 4
*/
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3444kb
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: 3656kb
input:
2 2 1 1 1
output:
4
result:
ok single line: '4'
Test #3:
score: 0
Accepted
time: 1ms
memory: 3396kb
input:
1 1 1
output:
2
result:
ok single line: '2'
Test #4:
score: 0
Accepted
time: 1ms
memory: 3500kb
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: 2ms
memory: 3524kb
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: 1ms
memory: 3416kb
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: 3572kb
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: 0ms
memory: 3548kb
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: 2ms
memory: 3548kb
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: 0ms
memory: 3416kb
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: 1ms
memory: 3576kb
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: 3456kb
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: -100
Wrong Answer
time: 1ms
memory: 3524kb
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:
264
result:
wrong answer 1st lines differ - expected: '266', found: '264'