QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#226507#2500. Collecting Stamps 3Camillus0 12ms214652kbC++202.2kb2023-10-26 01:29:562023-10-26 01:29:56

Judging History

This is the latest submission verdict.

  • [2023-10-26 01:29:56]
  • Judged
  • Verdict: 0
  • Time: 12ms
  • Memory: 214652kb
  • [2023-10-26 01:29:56]
  • Submitted

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

    memset(dp, 7, sizeof(dp));

    static const int INF = dp[0][0][0][0];

    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] == INF) {
                        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: 4ms
memory: 214572kb

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: 3ms
memory: 214596kb

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: 12ms
memory: 214592kb

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: 3ms
memory: 214588kb

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

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

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%