Submission #796460

#TimeUsernameProblemLanguageResultExecution timeMemory
796460cfhaterCollecting Stamps 3 (JOI20_ho_t3)C++17
5 / 100
243 ms53376 KiB
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define int ll

const int INF = 1e18, MAXN = 205, MOD = 1e9 + 7;

int n, l;
int dp[MAXN][MAXN][MAXN][2];

int dist(int a, int b) {
    return min((a - b + l) % l, (b - a + l) % l);
}

signed main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);

    cin >> n >> l;
    vector<pair<int, int>> left(n);
    for (auto& i : left)
        cin >> i.first;
    for (auto& i : left)
        cin >> i.second;
    auto right = left;
    left.push_back({0, 0});
    right.push_back({l, 0});
    sort(all(left));
    sort(rall(right));

    int res = 0;
    for (int lb = 0; lb <= n; lb++)
        for (int rb = 0; lb + rb <= n; rb++)
            for (int cnt = 0; cnt <= n; cnt++)
                dp[lb][rb][cnt][0] = dp[lb][rb][cnt][1] = INF;
    for (int lb = 1; lb <= n; lb++) {
        if (dist(0, left[lb].first) <= left[lb].second) {
            dp[lb][0][1][0] = dist(0, left[lb].first);
            res = 1;
        }
    }
    for (int rb = 1; rb <= n; rb++) {
        if (dist(0, right[rb].first) <= right[rb].second) {
            dp[0][rb][1][1] = dist(0, right[rb].first);
            res = 1;
        }
    }

    for (int lb = 0; lb <= n; lb++) {
        for (int rb = 0; lb + rb <= n; rb++) {
            for (int cnt = 2; cnt <= n; cnt++) {
                if (lb > 0)
                    dp[lb][rb][cnt][0] = min(dp[lb][rb][cnt][0], dp[lb - 1][rb][cnt][0] + dist(left[lb - 1].first, left[lb].first));
                if (rb > 0)
                    dp[lb][rb][cnt][0] = min(dp[lb][rb][cnt][0], dp[lb][rb - 1][cnt][1] + dist(right[rb - 1].first, left[lb].first));
                if (lb > 0 and dp[lb - 1][rb][cnt - 1][0] + dist(left[lb - 1].first, left[lb].first) <= left[lb].second)
                    dp[lb][rb][cnt][0] = min(dp[lb][rb][cnt][0], dp[lb - 1][rb][cnt - 1][0] + dist(left[lb - 1].first, left[lb].first));
                if (lb > 0 and dp[lb - 1][rb][cnt - 1][1] + dist(right[rb].first, left[lb].first) <= left[lb].second)
                    dp[lb][rb][cnt][0] = min(dp[lb][rb][cnt][0], dp[lb - 1][rb][cnt - 1][1] + dist(right[rb].first, left[lb].first));

                if (lb > 0)
                    dp[lb][rb][cnt][1] = min(dp[lb][rb][cnt][1], dp[lb - 1][rb][cnt][0] + dist(left[lb - 1].first, right[rb].first));
                if (rb > 0)
                    dp[lb][rb][cnt][1] = min(dp[lb][rb][cnt][1], dp[lb][rb - 1][cnt][1] + dist(right[rb - 1].first, right[rb].first));
                if (rb > 0 and dp[lb][rb - 1][cnt - 1][1] + dist(right[rb - 1].first, right[rb].first) <= right[rb].second)
                    dp[lb][rb][cnt][1] = min(dp[lb][rb][cnt][1], dp[lb][rb - 1][cnt - 1][1] + dist(right[rb - 1].first, right[rb].first));
                if (rb > 0 and dp[lb][rb - 1][cnt - 1][0] + dist(left[lb].first, right[rb].first) <= right[rb].second)
                    dp[lb][rb][cnt][1] = min(dp[lb][rb][cnt][1], dp[lb][rb - 1][cnt - 1][0] + dist(left[lb].first, right[rb].first));

                dp[lb][rb][cnt][0] = min(dp[lb][rb][cnt][0], dp[lb][rb][cnt][1] + dist(left[lb].first, right[rb].first));
                dp[lb][rb][cnt][1] = min(dp[lb][rb][cnt][1], dp[lb][rb][cnt][0] + dist(left[lb].first, right[rb].first));

                if (dp[lb][rb][cnt][0] < INF or dp[lb][rb][cnt][1] < INF)
                    res = max(res, cnt);
                if (lb == 0 and cnt >= 4 and rb >= 4)
                    int x = 0;
            }
        }
    }

    cout << res;
}

Compilation message (stderr)

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:80:25: warning: unused variable 'x' [-Wunused-variable]
   80 |                     int x = 0;
      |                         ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...