Submission #201032

#	Time	Username	Problem	Language	Result	Execution time	Memory
201032		HellAngel	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	133 ms	69984 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 7;
const int maxn = 207;

int dp[maxn][maxn][maxn][2], x[maxn], t[maxn], n, l, sum, ans;

/// left, right, cnt, curpos

int Dist(int i, int j)
{
    return min(abs(i - j), min(i, l - i) + min(j, l - j));
}

void Minimize(int &a, int b, bool check)
{
    if(check)
    a = min(a, b);
}

int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin);
    cin >> n >> l;
    fill_n(&dp[0][0][0][0], maxn * maxn * maxn * 2, inf);
    for(int i = 1; i <= n; i++) cin >> x[i];
    for(int i = 1; i <= n; i++) cin >> t[i];
    dp[0][0][0][0] = dp[0][0][0][1] = 0;
    for(int len = 1; len <= n; len++)
    {
        for(int r = 0; r <= len; r++)
        {
            int l = len - r;
            for(int cnt = 0; cnt <= len; cnt++)
            {
                if(cnt < len)
                {
                    if(l > 0)
                    {
                        Minimize(dp[l][r][cnt][0], dp[l - 1][r][cnt][0] + Dist(x[l], x[l - 1]), 1);
                        Minimize(dp[l][r][cnt][0], dp[l - 1][r][cnt][1] + Dist(x[n - r + 1], x[l]), 1);
                    }
                    if(r > 0)
                    {
                        Minimize(dp[l][r][cnt][1], dp[l][r - 1][cnt][0] + Dist(x[l], x[n - r + 1]), 1);
                        Minimize(dp[l][r][cnt][1], dp[l][r - 1][cnt][1] + Dist(x[n - r + 2], x[n - r + 1]), 1);
                    }
                }
                if(cnt > 0)
                {
                    if(l > 0)
                    {
                        int val;
                        val = dp[l - 1][r][cnt - 1][0] + Dist(x[l], x[l - 1]);
                        Minimize(dp[l][r][cnt][0], val, val <= t[l]);
                        val = dp[l - 1][r][cnt - 1][1] + Dist(x[n - r + 1], x[l]);
                        Minimize(dp[l][r][cnt][0], val, val <= t[l]);
                    }
                    if(r > 0)
                    {
                        int val;
                        val = dp[l][r - 1][cnt - 1][0] + Dist(x[l], x[n - r + 1]);
                        Minimize(dp[l][r][cnt][1], val, val <= t[n - r + 1]);
                        val = dp[l][r - 1][cnt - 1][1] + Dist(x[n - r + 2], x[n - r + 1]);
                        Minimize(dp[l][r][cnt][1], val, val <= t[n - r + 1]);
                    }
                }
                if(dp[l][r][cnt][0] != inf) 
                {
                    ans = max(ans, cnt);
                }
                if(dp[l][r][cnt][1] != inf) ans = max(ans, cnt);
            }
        }
    }
    cout << ans;
}

Compilation message (stderr)

ho_t3.cpp: In function 'int32_t main()':
ho_t3.cpp:25:39: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
     if(fopen("test.inp", "r")) freopen("test.inp", "r", stdin);
                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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