Submission #761843

#	Time	Username	Problem	Language	Result	Execution time	Memory
761843		sysia	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	621 ms	462256 KiB

ho_t3

//Sylwia Sapkowska
#include <bits/stdc++.h>
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

#define int long long
typedef pair<int, int> T;
const int oo = 1e18, oo2 = 1e9+7, K = 30;
const int mod = 998244353;

void ckmin(int &a, int b){
    a = min(a, b);
}

void solve(){
    int n, all; cin >> n >> all;
    vector<int>x(n+2), t(n+2);
    for (int i = 1; i<=n; i++) cin >> x[i];
    for (int i = 1; i<=n; i++) cin >> t[i];
    t[0] = oo;
    t[n+1] = oo;
    int ans = 0;
    vector dp(n+3, vector<vector<vector<int>>>(n+3, vector<vector<int>>(n+3, vector<int>(2, oo))));
    dp[0][0][0][0] = dp[0][0][0][1] = 0;
    auto nxt = [&](int a){
        return (a+1)%(n+1);
    };
    auto prev = [&](int a){
        return a ? a - 1 : n;
    };
    auto dist = [&](int i, int j){
        int y = abs(x[i] - x[j]);
        return min(y, all-y);
    };
    for (int len = 2; len <= n+1; len++){
        // if (len > 3) break;
        for (int l = 0, r = len-1; l <= n; l++, r = nxt(r)){
            for (int ret = 0; ret <= n; ret++){
                int d;

                //dp[l][r][ret][rep]
                //[l+1, r]
                int L = nxt(l);
                int R = prev(r);

                d = dist(L, l);
                int get = (dp[L][r][ret][0] + d <= t[l]);
                ckmin(dp[l][r][ret+get][0], dp[L][r][ret][0] + d);

                d = dist(l, r);
                get = (dp[L][r][ret][1] + d <= t[l]);
                ckmin(dp[l][r][ret+get][0], dp[L][r][ret][1] + d);
            
                //[l, r-1]
                
                d = dist(R, r);
                
                get = (dp[l][R][ret][1] + d <= t[r]);
                ckmin(dp[l][r][ret+get][1], dp[l][R][ret][1] + d);


                d = dist(l, r);
                get = (dp[l][R][ret][0] + d <= t[r]);
                ckmin(dp[l][r][ret + get][1], dp[l][R][ret][0] + d);
            }   
        }
    }
    for (int len = 2; len <= n+1; len++){
        for (int l = 0, r = len-1; l <= n; l++, r = nxt(r)){
            for (int ret = 0; ret <= n; ret++){
                if (dp[l][r][ret][0] != oo || dp[l][r][ret][1] != oo){
                    debug(l, r, ret, dp[l][r][ret][0], dp[l][r][ret][1]);
                    ans = max(ans, ret);
                }
            }
        }
    }
    cout << ans << "\n";
}  

/*
//dp[l][k][x] --> //dp[l][r][y]
debug(k);
for (int rep = 0; rep < 2; rep++){
    int from = (rep ? k : l);
    for (int rep2 = 0; rep2 < 2; rep2++){
        int to = (rep ? r : l);
        int xx = dp[l][k][rep].second + dist(from, to);
        int get = (xx <= t[to]);
        ckmax(dp[l][r][rep2], {dp[l][k][rep].first+get, xx});
    }
    int from2 = (rep ? r : k);
    for (int rep2 = 0; rep2 < 2; rep2++){
        int to = (rep ? r : l);
        int xx = dp[k][r][rep].second + dist(from2, to);
        int get = (xx <= t[to]);
        ckmax(dp[l][r][rep2], {dp[k][r][rep].first+get, xx});
    }
}
if (k == r) break;
}
debug(l, r, dp[l][r][0], dp[l][r][1]);
// if (l == 0 && r == 1) exit(0);
*/

int32_t main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int t = 1;
    //cin >> t;
    while (t--) solve();

    return 0;
}

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