Submission #1115052

#	Time	Username	Problem	Language	Result	Execution time	Memory
1115052		staszic_ojuz	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	144 ms	127572 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n,l;
    cin>>n>>l;
    vector<long long> tr(n+1);
    vector<long long> tl(n+1);
    vector<long long> rd(n+1);
    vector<long long> ld(n+1);
    rd[0] = 0;
    ld[0] = 0;
    tr[0] = 0;
    tl[0] = 0;
    for(int i = 1;i<n+1;i++)
    {
        cin>>rd[i];
        ld[n-i+1] = l-rd[i];
    }
    for(int i = 1;i<n+1;i++)
    {
        cin>>tr[i];
        tl[n-i+1] = tr[i];
    }
    long long m = 1000000000;
    m *=m;
    long long dp[n+1][n+1][n+1][2];
    dp[0][0][0][0] = 0;
    dp[0][0][0][1] = 0;
    for(int i = 1;i<n+1;i++)
    {
        dp[0][0][i][0] = m;
        dp[0][0][i][1] = m;
    }
    for(int i = 1;i<n+1;i++)
    {
        for(int q = 0;q<n+1;q++)
        {
            dp[i][0][q][0] = m;
            dp[i][0][q][1] = m;
            dp[i][0][q][0] = dp[i-1][0][q][0]-ld[i-1]+ld[i];
            if(q!=0 && dp[i-1][0][q-1][0]+ld[i]-ld[i-1] <= tl[i])
            {
                dp[i][0][q][0] = min(dp[i][0][q][0],dp[i-1][0][q-1][0]+ld[i]-ld[i-1]);
            }
            dp[i][0][q][1] = 2*dp[i][0][q][0];
        }
    }
    for(int j = 1;j<n+1;j++)
    {
        for(int q = 0;q<n+1;q++)
        {
            dp[0][j][q][1] = m;
            dp[0][j][q][0] = m;
            dp[0][j][q][1] = dp[0][j-1][q][1]-rd[j-1]+rd[j];
            if(q!= 0 &&dp[0][j-1][q-1][1]+rd[j]-rd[j-1] <= tr[j])
            {
                dp[0][j][q][1] = min(dp[0][j][q][1],dp[0][j-1][q-1][1]+rd[j]-rd[j-1]);
            }
            dp[0][j][q][0] = 2*dp[0][j][q][1];
        }
    }

    for(int i = 1;i<n+1;i++)
    {
        for(int j = 1;j<n+1;j++)
        {
            for(int q = 0;q<n+1;q++)
            {

                dp[i][j][q][0] = m;
                dp[i][j][q][1] = m;
                if(i+j > n) continue;
                if(i!= 0)
                {
                    dp[i][j][q][0] = min(dp[i-1][j][q][0]-ld[i-1]+ld[i],dp[i-1][j][q][1]+rd[j]+ld[i]);
                }
                if(q!=0 && dp[i-1][j][q-1][0]+ld[i]-ld[i-1] <= tl[i])
                {
                    dp[i][j][q][0] = min(dp[i][j][q][0],dp[i-1][j][q-1][0]+ld[i]-ld[i-1]);
                }
                if(q!=0 && dp[i-1][j][q-1][1]+rd[j]+ld[i] <=tl[i])
                {
                    dp[i][j][q][0] = min(dp[i][j][q][0],dp[i-1][j][q-1][1]+ld[i]+rd[j]);
                }
                if(j != 0)
                {
                    dp[i][j][q][1] = min(dp[i][j-1][q][0]+ld[i]+rd[j],dp[i][j-1][q][1]-rd[j-1]+rd[j]);
                }
                if(q!= 0 && dp[i][j-1][q-1][0] + ld[i]+rd[j] <= tr[j])
                {
                    dp[i][j][q][1] = min(dp[i][j][q][1],dp[i][j-1][q-1][0] + ld[i]+rd[j]);
                }
                if(q != 0 && dp[i][j-1][q-1][1] + rd[j]-rd[j-1] <= tr[j])
                {
                    dp[i][j][q][1] = min(dp[i][j][q][1],dp[i][j-1][q-1][1]-rd[j-1]+rd[j]);
                }
            }
        }
    }
    int ans = 0;
    for(int i = 0;i<n+1;i++)
    {
        for(int j = 0;j<n+1;j++)
        {
            for(int q = 0;q<n+1;q++)
            {
                if(dp[i][j][q][0] < m) ans = max(ans,q);
                if(dp[i][j][q][1] < m) ans = max(ans,q);
            }
        }
    }
    cout<<ans;
}

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