Submission #1114703

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114703		tkwiatkowski	Collecting Stamps 3 (JOI20_ho_t3)	C++17	0 / 100	1 ms	564 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,l;
    cin>>n>>l;
    vector<int> tr(n);
    vector<int> tl(n);
    vector<int> rd(n+1);
    vector<int> ld(n+1);
    vector<pair<int,int>> cl(n);
    vector<pair<int,int>> cr(n);
    rd[0] = 0;
    ld[0] = 0;
    for(int i = 0;i<n;i++)
    {
        //cin>>rd[i+1];
        //ld[n-i] = l-rd[i+1];
        cin>>cr[i].first;
        cr[i].first%=l;
        cl[n-i-1].first =  l-cr[i].first;
    }
    for(int i = 0;i<n;i++)
    {
        //cin>>tr[i];
        //tl[n-i-1] = tr[i];
        cin>>cr[i].second;
        cl[n-i-1].second = cr[i].second;
    }
    sort(cl.begin(),cl.end());
    sort(cr.begin(),cr.end());
    for(int i = 0;i<n;i++)
    {
        rd[i+1] = cr[i].first;
        ld[i+1] = cl[i].first;
        tr[i] = cr[i].second;
        tl[i] = cl[i].second;
    }
    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-1])
            {
                //if(q==1&&i==1) cout<<"d"<<ld[i]<<" "<<ld[i-1]<<"\n";
                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-1])
            {
                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!= 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-1])
                {
                    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-1])
                {
                    dp[i][j][q][0] = min(dp[i][j][q][0],dp[i-1][j][q-1][0]+ld[i]+rd[j]);
                }
                //if((i == 1 && j == 1)&&(q == 1))
                //{cout<<"a"<<"\n";}
                if(j != 0)
                {
                    /*if((i == 1 && j == 1)&&(q == 1))
                    {
                        cout<<dp[i][j][q][1]<<"\n";
                    }*/
                    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((i == 1 && j == 1)&&(q == 1))
                    {
                        cout<<dp[i][j][q][1]<<"\n";
                    }*/
                }
                if(q!= 0 && dp[i][j-1][q-1][0] + ld[i]+rd[j] <= tr[j-1])
                {
                    //if((i == 1 && j == 1)&&(q == 1)) cout<<"b"<<"\n";
                    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-1])
                {
                    //if((i == 1 && j == 1)&&(q == 1)) cout<<"a"<<"\n";
                    dp[i][j][q][1] = min(dp[i][j][q][1],dp[i][j-1][q-1][0]-rd[j-1]+rd[j]);
                }
            }
        }
    }
    /*for(int i = 0;i<n+1;i++)
    {
        for(int j = 0;j<n+1;j++)
        {
            for(int q = 0;q<n+1;q++)
            {
                for(int w = 0;w<2;w++)
                {
                    cout<<dp[i][j][q][w]<<" dp["<<i<<"]["<<j<<"]["<<q<<"]["<<w<<"]\n";;
                }
            }
        }
    }*/
    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: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 75