Submission #202459

#	Time	Username	Problem	Language	Result	Execution time	Memory
202459		Kastanda	Collecting Stamps 3 (JOI20_ho_t3)	C++11	100 / 100	168 ms	143356 KiB

ho_t3

// In The Name Of The Queen
#include<bits/stdc++.h>
using namespace std;
const int N = 209;
int n, L, X[N], T[N];
long long dp[N][N][N][2];
inline void SMin(long long &a, long long b)
{
    a = min(a, b);
}
int main()
{
    scanf("%d%d", &n, &L);
    for (int i = 1; i <= n; i ++)
        scanf("%d", &X[i]);
    for (int i = 1; i <= n; i ++)
        scanf("%d", &T[i]);
    memset(dp, 63, sizeof(dp));
    dp[1][n + 1][X[1] <= T[1]][0] = X[1];
    dp[0][n][L - X[n] <= T[n]][1] = L - X[n];
    for (int len = n; len; len --)
        for (int l = 0, r = len; r <= n + 1; l ++, r ++)
            for (int c = 0; c <= l + n + 1 - r; c ++)
            {
                /// w = 0 : We're at l.
                // Increase l :
                SMin(dp[l + 1][r][c + (dp[l][r][c][0] + X[l + 1] - X[l] <= T[l + 1])][0], dp[l][r][c][0] + X[l + 1] - X[l]);
                // Decrease r :
                SMin(dp[l][r - 1][c + (dp[l][r][c][0] + L - X[r - 1] + X[l] <= T[r - 1])][1], dp[l][r][c][0] + L - X[r - 1] + X[l]);
                /// w = 1 : We're at r.
                // Increase l :
                SMin(dp[l + 1][r][c + (dp[l][r][c][1] + L - X[r] + X[l + 1] <= T[l + 1])][0], dp[l][r][c][1] + L - X[r] + X[l + 1]);
                // Decrease r :
                SMin(dp[l][r - 1][c + (dp[l][r][c][1] + X[r] - X[r - 1] <= T[r - 1])][1], dp[l][r][c][1] + X[r] - X[r - 1]);
            }
    int Mx = 0;
    for (int l = 0; l <= n; l ++)
        for (int c = 0; c <= n; c ++)
            for (int w = 0; w <= 1; w ++)
                if (dp[l][l + 1][c][w] <= 1LL * n * L)
                    Mx = max(Mx, c);
    return !printf("%d\n", Mx);
}

Compilation message (stderr)

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:13:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d", &n, &L);
     ~~~~~^~~~~~~~~~~~~~~~
ho_t3.cpp:15:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &X[i]);
         ~~~~~^~~~~~~~~~~~~
ho_t3.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &T[i]);
         ~~~~~^~~~~~~~~~~~~

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