QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#133725#4931. Comic Binge4k2kok#TL 8ms82416kbC++201.8kb2023-08-02 13:33:562023-08-02 13:34:11

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-08-02 13:34:11]
  • 评测
  • 测评结果:TL
  • 用时:8ms
  • 内存:82416kb
  • [2023-08-02 13:33:56]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define PI acos(-1)
#define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0)
#define mem(a,b) memset((a),(b),sizeof(a))
typedef long long ll;
typedef unsigned long long ull;
#define int long long

const int maxn = 1e5 + 10;

int n, dp[1010][10010], a[1010], b[1010], pre[1010], min_ans = INF;

bool dfs(int pos, int gap, int used) {
    // if (pos == n) return 1;
    if (pos > n) return 0;
    if(gap > min_ans) return 1;
    // if (~dp[pos][gap]) return dp[pos][gap];
    bool ans = 0;
    bool nowans = dfs(pos + 1, max(gap, used + b[pos] - pre[pos - 1]), used + b[pos]);
    ans = ans || nowans;
    if (nowans || pos == n) {
        dp[pos][max(gap, used + b[pos] - pre[pos - 1])] = 1;
    }
    nowans = dfs(pos + 2, max(gap, used + b[pos] - pre[pos - 1]), used + b[pos]);
    ans = ans || nowans;
    if (nowans || pos == n) {
        dp[pos][max(gap, used + b[pos] - pre[pos - 1])] = 1;
    }
    if(pos == n) {min_ans = min(min_ans, max(gap, used + b[pos] - pre[pos - 1])) ;return 1;}
    else return ans;
}

void solve() {
    memset(dp, -1, sizeof dp);
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        pre[i] = pre[i - 1] + a[i];
    }
    for (int i = 1; i <= n; i++) {
        cin >> b[i];
    }
    dfs(1, 0, 0);
    int ans = 0;
    // for (int i = 0; i <= 100; i++) {
    //     cerr << dp[n][i] << ' ';
    // }
    // cerr << '\n';
    // for (int i = 0; i <= 10000; i++) {
    //     if (dp[n][i] == 1) {
    //         ans = i;
    //         break;
    //     }
    // }
    cout << pre[n] + min_ans << '\n';
}

signed main(){
    // io;
    int T = 1;
    //cin >> T;
    while(T--) {
        solve();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 82324kb

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: 8ms
memory: 82396kb

input:

2
2 1
1 1

output:

4

result:

ok single line: '4'

Test #3:

score: 0
Accepted
time: 1ms
memory: 82416kb

input:

1
1
1

output:

2

result:

ok single line: '2'

Test #4:

score: -100
Time Limit Exceeded

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:


result: