Submission #212548

#	Time	Username	Problem	Language	Result	Execution time	Memory
212548		DystoriaX	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	83 ms	68224 KiB

ho_t3

#include <bits/stdc++.h>

using namespace std;

int n, l;
int x[210], t[210];
int dp[210][210][210][2];
const int MAX = 1e9 + 1;

int getDist(int i, int j){
    int ret = x[i] - x[j]; ret %= l;

    if(ret < 0) ret += l;

    return min(ret, l - ret);
}

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]);
    
    for(int i = 0; i <= n + 1; i++)
        for(int j = 0; j <= n + 1; j++)
            for(int k = 0; k <= n + 1; k++)
                dp[i][j][k][0] = dp[i][j][k][1] = MAX;

    dp[0][n + 1][0][0] = dp[0][n + 1][0][1] = 0;

    for(int len = n + 1; len >= 1; len--){
        for(int i = 0; i + len <= n + 1; i++){
            int j = i + len;

            for(int k = 0; k <= n; k++){
                // if(k == 5 && dp[i][j][k][0] != MAX) printf("dp[%d][%d][%d][0] = %d\n", i, j, k, dp[i][j][k][0]);
                // if(k == 5 && dp[i][j][k][1] != MAX) printf("dp[%d][%d][%d][1] = %d\n", i, j, k, dp[i][j][k][1]);
            
                int dist;

                //Position on right [clockwise]
                if(dp[i][j][k][0] != MAX){
                    //From i to i + 1
                    dist = getDist(i, i + 1);
                    dist += dp[i][j][k][0];

                    if(dist <= t[i + 1])
                        dp[i + 1][j][k + 1][0] = min(dp[i + 1][j][k + 1][0], dist);
                    else 
                        dp[i + 1][j][k][0] = min(dp[i + 1][j][k][0], dist);

                    //From i to j - 1
                    dist = getDist(i, j - 1);
                    dist += dp[i][j][k][0];

                    if(dist <= t[j - 1])
                        dp[i][j - 1][k + 1][1] = min(dp[i][j - 1][k + 1][1], dist);
                    else
                        dp[i][j - 1][k][1] = min(dp[i][j - 1][k][1], dist);
                }

                //Position on left [counter clockwise]
                if(dp[i][j][k][1] != MAX){
                    //From j to j - 1
                    dist = getDist(j, j - 1);
                    dist += dp[i][j][k][1];

                    if(dist <= t[j - 1])
                        dp[i][j - 1][k + 1][1] = min(dp[i][j - 1][k + 1][1], dist);
                    else
                        dp[i][j - 1][k][1] = min(dp[i][j - 1][k][1], dist);

                    //From j to i + 1
                    dist = getDist(j, i + 1);                    
                    dist += dp[i][j][k][1];

                    if(dist <= t[i + 1])
                        dp[i + 1][j][k + 1][0] = min(dp[i + 1][j][k + 1][0], dist);
                    else 
                        dp[i + 1][j][k][0] = min(dp[i + 1][j][k][0], dist);
                }
            }
        }
    }

    int ans = 0;

    for(int i = 0; i <= n; i++)
        for(int cnt = 0; cnt <= n; cnt++)
            if(dp[i][i + 1][cnt][0] != MAX || dp[i][i + 1][cnt][1] != MAX)
                ans = max(ans, cnt);

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

    return 0;
}

Compilation message (stderr)

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:19: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:21:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= n; i++) scanf("%d", &x[i]);
                                 ~~~~~^~~~~~~~~~~~~
ho_t3.cpp:22:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= n; i++) scanf("%d", &t[i]);
                                 ~~~~~^~~~~~~~~~~~~

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