Submission #817192

#	Time	Username	Problem	Language	Result	Execution time	Memory
817192		reitracn	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	95 ms	129452 KiB

ho_t3

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 1e18;

int dp[202][202][202][2];


const int LEFT_SIDE = 0, RIGHT_SIDE = 1;
// posG, posD, nbStamps, side ==> temps min.

/////CHECK if posG+posD < N

signed main()
{
    for(int pG = 0; pG< 202; pG++)
    {
        for(int pD = 0; pD < 202; pD++)
        {
            for(int nbStamps = 0; nbStamps < 202; nbStamps++)
            {
                dp[pG][pD][nbStamps][0] = INF;
                dp[pG][pD][nbStamps][1] = INF;
            }
        }
    }
    dp[0][0][0][0] = dp[0][0][0][1] = 0;
    
    int N, lacLen;
    scanf("%lld%lld", &N, &lacLen);

    vector<int > posLeft(N+1);
    vector<int > expTimeLeft(N+1);

    vector<int > posRight(N+1);
    vector<int > expTimeRight(N+1);

    for(int iS = 1, iR = N; iS <= N; iS++, iR--)
    {
        int posAct;
        scanf("%lld", &posAct);
        posLeft[iS] = posAct;
        posRight[iR] = lacLen-posAct;
    }
    for(int iS = 1, iR = N; iS <= N; iS++, iR--)
    {
        int expTimeAct;
        scanf("%lld", &expTimeAct);
        expTimeLeft[iS] = expTimeAct;
        expTimeRight[iR] = expTimeAct;
    }
    /*for(int i= 1; i<=N; i++)
    {
        printf("%lld/%lld ", posLeft[i], expTimeLeft[i]);
    }
    printf("\n");
    for(int i= 1; i<=N; i++)
    {
        printf("%lld/%lld ", posRight[i], expTimeRight[i]);
    }
    printf("\n");*/
    
    int ans = 0;
    for(int nbStampsGot = 0; nbStampsGot <= N; nbStampsGot++)
    {
        for(int pL = 0; pL <= N; pL++)
        {
            for(int pR = 0; pR <= N - pL-1; pR++)/////////////////////////
            {
                for(int side = 0; side < 2; side ++)
                {
                    if(dp[pL][pR][nbStampsGot][side] == INF)
                        continue;
                    int tpsBefore = dp[pL][pR][nbStampsGot][side];
                    int tpsGauche, tpsDroite;
                    if(side == LEFT_SIDE)
                    {
                        tpsGauche = tpsBefore + abs(posLeft[pL+1] - posLeft[pL]);//////////////// 
                        tpsDroite = tpsBefore + posLeft[pL] + posRight[pR+1];////////////////
                    }
                    else
                    {
                        tpsGauche = tpsBefore + posRight[pR] + posLeft[pL+1];
                        tpsDroite = tpsBefore + abs(posRight[pR+1] - posRight[pR]);
                    }

                    if(tpsGauche <= expTimeLeft[pL +1])
                    {
                        dp[pL+1][pR][nbStampsGot+1][LEFT_SIDE] = min(dp[pL+1][pR][nbStampsGot+1][LEFT_SIDE], tpsGauche);
                        ans = max(ans, nbStampsGot+1);
                    }
                    else
                    {
                        dp[pL+1][pR][nbStampsGot][LEFT_SIDE] = min(dp[pL+1][pR][nbStampsGot][LEFT_SIDE], tpsGauche);
                    }

                    if(tpsDroite <= expTimeRight[pR +1])
                    {
                        dp[pL][pR+1][nbStampsGot+1][RIGHT_SIDE] = min(dp[pL][pR+1][nbStampsGot+1][RIGHT_SIDE], tpsDroite);
                        ans = max(ans, nbStampsGot+1);
                    }
                    else
                    {
                        dp[pL][pR+1][nbStampsGot][RIGHT_SIDE] = min(dp[pL][pR+1][nbStampsGot][RIGHT_SIDE], tpsDroite);
                    }
                }
            }
        }
    }

    printf("%lld\n", ans);

}

Compilation message (stderr)

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   30 |     scanf("%lld%lld", &N, &lacLen);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
ho_t3.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |         scanf("%lld", &posAct);
      |         ~~~~~^~~~~~~~~~~~~~~~~
ho_t3.cpp:48:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 |         scanf("%lld", &expTimeAct);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~

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