Submission #1245436

#	Time	Username	Problem	Language	Result	Execution time	Memory
1245436		AHOKA	Collecting Stamps 3 (JOI20_ho_t3)	C++20	100 / 100	80 ms	141384 KiB

ho_t3

#include <bits/stdc++.h>

#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")

using namespace std;
 
#define threesum cin.tie(NULL); cout.tie(NULL); ios_base::sync_with_stdio(false)
#define all(a) a.begin(), a.end()
#define F first
#define S second
#define int long long
#define pii pair<int, int>
#define ppp pair<int, pii>
#define dout cout << fixed << setprecision(15)
#define mid ((l + r) >> 1)
#define lc (id << 1)
#define rc (lc + 1)

const int maxn = 2e5 + 10, maxm = 2e2 + 10, oo = 1e18, lg = 19, sq = 1400, mod = 998244353;

int n, ln, ans;

int x[maxm], t[maxm];

int dp[2][maxm][maxm][maxm];

int d(int x, int y){
    return min(abs(x - y), ln - (abs(x - y)));
}

void solve()
{
    cin >> n >> ln;
    
    for (int i = 1; i <= n; i++)
        cin >> x[i];
    for (int i = 1; i <= n;i++)
        cin >> t[i];

    x[0] = 0;
    x[n + 1] = ln;

    t[0] = -oo;
    t[n + 1] = -oo;

    for (int b = 0; b < 2;b++)
        for (int l = 0; l <= n + 5; l++)
            for (int r = 0; r <= n + 5; r++)
                for (int k = 0; k <= n + 5;k++)
                    dp[b][l][r][k] = oo;

    dp[0][0][n + 1][0] = 0;
    dp[1][0][n + 1][0] = 0;

    for (int l = 0; l < n; l++)
    	for (int r = n + 1; r - 1 > l; r--)
    		for (int k = 0; k <= n; k++){
				int tm;

				tm = min(dp[0][l][r][k] + d(x[l + 1], x[l]), dp[1][l][r][k] + d(x[l + 1], x[r]));

				if(tm <= t[l + 1])
					dp[0][l + 1][r][k + 1] = min(dp[0][l + 1][r][k + 1], tm);

				else 
					dp[0][l + 1][r][k] = min(dp[0][l + 1][r][k], tm);

				tm = min(dp[0][l][r][k] + d(x[r - 1], x[l]), dp[1][l][r][k] + d(x[r - 1], x[r]));

				if(tm <= t[r - 1])
					dp[1][l][r - 1][k + 1] = min(dp[1][l][r - 1][k + 1], tm);

				else 
					dp[1][l][r - 1][k] = min(dp[1][l][r - 1][k], tm);
            }

    for (int b = 0; b < 2;b++)
        for (int l = 0; l <= n + 5; l++)
            for (int r = 0; r <= n + 5; r++)
                for (int k = 0; k <= n + 5;k++)
                    if(dp[b][l][r][k] < oo)
                        ans = max(ans, k);

    cout << ans;
}

signed main()
{
    threesum;
    int t = 1;
    //cin >> t;
    while(t--)
        solve();
}

/*
10 87
9 23 33 38 42 44 45 62 67 78
15 91 7 27 31 53 12 91 89 46
*/

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