Submission #206994

#	Time	Username	Problem	Language	Result	Execution time	Memory
206994		wiwiho	Collecting Stamps 3 (JOI20_ho_t3)	C++14	0 / 100	5 ms	380 KiB

ho_t3

//#define NDEBUG

#include <bits/stdc++.h>
#include <bits/extc++.h>

#define StarBurstStream ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define iter(a) a.begin(), a.end()
#define riter(a) a.rbegin(), a.rend()
#define lsort(a) sort(iter(a))
#define gsort(a) sort(riter(a))
#define mp(a, b) make_pair(a, b)
#define pb(a) push_back(a)
#define eb(a) emplace_back(a)
#define pf(a) push_front(a)
#define pob pop_back()
#define pof pop_front()
#define F first
#define S second
#define printv(a, b) {bool pvaspace=false; \
for(auto pva : a){ \
    if(pvaspace) b << " "; pvaspace=true;\
    b << pva;\
}\
b << "\n";}
#define pii pair<int, int>
#define pll pair<ll, ll>
#define tiii tuple<int, int, int>
#define mt make_tuple
#define gt(t, i) get<i>(t)
#define iceil(a, b) ((a) / (b) + !!((a) % (b)))

//#define TEST

typedef long long ll;
typedef unsigned long long ull;

using namespace std;
using namespace __gnu_pbds;

const ll MOD = 1000000007;
const ll MAX = 2147483647;

template<typename A, typename B>
ostream &operator<<(ostream &o, pair<A, B> p){
    return o << '(' << p.F << ',' << p.S << ')';
}

int dis(int a, int b, int l){
    return min(abs(a - b), l - abs(a - b));
}

int main(){
    StarBurstStream

    int n, L;
    cin >> n >> L;

    vector<int> x(n), t(n);
    for(int i = 0; i < n; i++) cin >> x[i];
    for(int i = 0; i < n; i++) cin >> t[i];

    vector<vector<vector<int>>> dpl(n, vector<vector<int>>(n, vector<int>(n + 1, 1 << 30))),
            dpr(n, vector<vector<int>>(n, vector<int>(n + 1, 1 << 30)));

    for(int len = 1; len <= n; len++){
        for(int l = n - len; ; l = (l + 1) % n){
            int r = (l + len - 1) % n;
            if(len == 1){
                dpl[l][r][0] = dis(x[l], 0, L);
                dpr[l][r][0] = dis(x[l], 0, L);
                if(dis(x[l], 0, L) <= t[l]){
                    dpl[l][r][1] = dis(x[l], 0, L);
                    dpr[l][r][1] = dis(x[l], 0, L);
                }
                if(l == 0) break;
                continue;
            }

            int l1 = (l + 1) % n;
            int r1 = (r - 1 + n) % n;

            dpl[l][r][0] = min(dpl[l1][r][0] + dis(x[l], x[l1], L), dpr[l1][r][0] + dis(x[l], x[r], L));
            dpr[l][r][0] = min(dpr[l][r1][0] + dis(x[r], x[r1], L), dpl[l][r1][0] + dis(x[l], x[r], L));
            for(int c = 1; c <= n; c++){
                dpl[l][r][c] = min(dpl[l][r][c], dpl[l1][r][c] + dis(x[l], x[l1], L));
                dpl[l][r][c] = min(dpl[l][r][c], dpr[l1][r][c] + dis(x[l], x[r], L));
                if(dpl[l1][r][c - 1] + dis(x[l], x[l1], L) <= t[l])
                    dpl[l][r][c] = min(dpl[l][r][c], dpl[l1][r][c - 1] + dis(x[l], x[l1], L));
                if(dpr[l1][r][c - 1] + dis(x[l], x[r], L) <= t[l])
                    dpl[l][r][c] = min(dpl[l][r][c], dpr[l1][r][c - 1] + dis(x[l], x[r], L));

                dpr[l][r][c] = min(dpr[l][r][c], dpr[l][r1][c] + dis(x[r], x[r1], L));
                dpr[l][r][c] = min(dpr[l][r][c], dpl[l][r1][c] + dis(x[r], x[l], L));
                if(dpr[l][r1][c - 1] + dis(x[r], x[r1], L) <= t[r])
                    dpr[l][r][c] = min(dpr[l][r][c], dpr[l][r1][c - 1] + dis(x[r], x[r1], L));
                if(dpl[l][r1][c - 1] + dis(x[r], x[l], L) <= t[r])
                    dpr[l][r][c] = min(dpr[l][r][c], dpl[l][r1][c - 1] + dis(x[r], x[l], L));
            }

            if(l == 0) break;
        }
    }

    int ans = 0;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            for(int k = 0; k <= n; k++){
                if(dpl[i][j][k] != (1 << 30) || dpr[i][j][k] != (1 << 30)){
//                    cerr << i << " " << j << " " << k << "\n";
                    ans = max(ans, k);
                }
            }
        }
    }

    cout << ans << "\n";

    return 0;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 75