QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#226508#2500. Collecting Stamps 3Camillus0 19ms214528kbC++202.3kb2023-10-26 01:31:222023-10-26 01:31:23

Judging History

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

  • [2023-10-26 01:31:23]
  • 评测
  • 测评结果:0
  • 用时:19ms
  • 内存:214528kb
  • [2023-10-26 01:31:22]
  • 提交

answer

/// @author Camillus
#include <bits/stdc++.h>

using ll = long long;
using namespace std;

int dp[300][300][300][2];

int x[300][2];
int t[300][2];

int min_equal(int &first, int second) {
    return first = min(first, second);
}

signed main() {
#ifndef LOCAL
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
#else
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif

    for (auto &a : dp) {
        for (auto &b : a) {
            for (auto &c : b) {
                for (auto &d : c) {
                    d = INT32_MAX;
                }
            }
        }
    }

    dp[0][0][0][0] = 0;

    int n, l;
    cin >> n >> l;

    for (int i = 1; i <= n; i++) {
        cin >> x[i][0];
        x[n - i + 1][1] = l - x[i][0];
    }

    for (int i = 1; i <= n; i++) {
        cin >> t[i][0];
        t[n - i + 1][1] = t[i][0];
    }

    int ans = 0;

    auto dist = [&l](int x, int y) {
        return min(abs(x - y), l - abs(x - y));
    };

    for (int c = 0; c <= n; c++) {
        for (int l = 0; l <= n; l++) {
            for (int r = 0; r <= n; r++) {
                for (int tA : {0, 1}) {
                    if (dp[c][l][r][tA] == INT32_MAX) {
                        continue;
                    } else {
                        ans = max(ans, c);
                    }

                    if (l + r >= n) {
                        continue;
                    }

                    int posA = (tA == 0 ? x[l][0] : x[r][1]);

                    for (int tB : {0, 1}) {
                        if (l + (tB == 0) > n || r + (tB == 1) > n) {
                            continue;
                        }

                        int posB = (tB == 0 ? x[l + 1][0] : x[r + 1][1]);
                        int timeB = (tB == 0 ? t[l + 1][0] : t[r + 1][1]);

                        int cur = dp[c][l][r][tA] + dist(posA, posB);

                        if (cur <= timeB) {
                            min_equal(dp[c + 1][l + (tB == 0)][r + (tB == 1)][tB], cur);
                        } else {
                            min_equal(dp[c][l + (tB == 0)][r + (tB == 1)][tB], cur);
                        }
                    }
                }
            }
        }
    }

    cout << ans << '\n';
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 5
Accepted
time: 8ms
memory: 214528kb

input:

5 180
137 149 164 167 171
18 76 14 55 116

output:

3

result:

ok single line: '3'

Test #2:

score: 0
Accepted
time: 19ms
memory: 214356kb

input:

5 198
5 12 18 190 192
16 43 200 33 0

output:

4

result:

ok single line: '4'

Test #3:

score: 0
Accepted
time: 3ms
memory: 214296kb

input:

9 198
3 17 22 33 43 44 48 54 65
0 17 29 32 38 46 45 54 66

output:

5

result:

ok single line: '5'

Test #4:

score: 0
Accepted
time: 0ms
memory: 214352kb

input:

6 171
22 30 46 85 96 149
18 179 19 69 87 96

output:

3

result:

ok single line: '3'

Test #5:

score: 0
Accepted
time: 3ms
memory: 214308kb

input:

7 198
5 8 14 188 191 194 197
7 18 50 69 80 35 8

output:

7

result:

ok single line: '7'

Test #6:

score: -5
Wrong Answer
time: 12ms
memory: 214484kb

input:

12 198
71 72 83 94 108 112 119 140 142 143 166 174
124 119 124 111 91 94 85 48 60 63 40 32

output:

11

result:

wrong answer 1st lines differ - expected: '9', found: '11'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%