Submission #224040

#	Time	Username	Problem	Language	Result	Execution time	Memory
224040		dwsc	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	516 ms	134136 KiB

ho_t3

#include <bits/stdc++.h>
#define int long long
using namespace std;
int memo[210][210][210][2];
int pos[210],reach[210];
int n,l;
int dp(int left,int right,int num,int side){
    if (num < 0) return 1e18;
    if (left == 0 && right == 0){
        if (num == 0) return 0;
        return 1e18;
    }
    if (memo[left][right][num][side] != -1) return memo[left][right][num][side];
    if (side){
        int mintime = 1e18;
        if (right != 0){
            int temp1 = min(dp(left,right-1,num-1,1)+pos[right]-pos[right-1],dp(left,right-1,num-1,0)+(pos[right]+l-pos[left])%l);
            if (temp1 <= reach[right]) mintime = min(mintime,temp1);
            int temp2 = min(dp(left,right-1,num,1)+pos[right]-pos[right-1],dp(left,right-1,num,0)+(pos[right]+l-pos[left])%l);
            mintime = min(mintime,temp2);
        }
       //if (num == 6)cout << left << " " << right << " " << num << " " << side << " " << mintime << "\n";
        return memo[left][right][num][side] = mintime;
    }
    else{
        int mintime = 1e18;
        if (left != 0){
            int temp1 = min(dp((left+1)%n,right,num-1,1)+(pos[right]+l-pos[left])%l,dp((left+1)%n,right,num-1,0)+(pos[(left+1)%n]+l-pos[left])%l);
            if (temp1 <= reach[left]) mintime = min(mintime,temp1);
            int temp2 = min(dp((left+1)%n,right,num,1)+(pos[right]+l-pos[left])%l,dp((left+1)%n,right,num,0)+(pos[(left+1)%n]+l-pos[left])%l);
            mintime = min(mintime,temp2);
        }
        //if (num == 6)cout << left << " " << right << " " << num << " " << side << " " << mintime << "\n";
        return memo[left][right][num][side] = mintime;
    }
}
main(){
    cin >> n >> l;
    for (int i = 0; i <= n; i++) for (int j = 0; j <= n; j++) for (int k = 0; k <= n; k++) memo[i][j][k][0] = memo[i][j][k][1] = -1;
    for (int i = 1; i <= n; i++) cin >> pos[i];
    for (int i = 1; i <= n; i++) cin >> reach[i];
    n++;
    pos[0] = 0;
    reach[0] = 1e18;
    dp(5,1,3,0);
    int ans = 0;
    for (int i = 1; i < n; i++){
        for (int j = 0; j < n; j++){
            for (int k = j+1; k <= n; k++){
                //cout << j << " " << k%n << "hi\n";
                if (min(dp(k%n,j,i,0),dp(k%n,j,i,1)) != 1e18) ans = i;
            }
        }
    }
    cout << ans;
}

Compilation message (stderr)

ho_t3.cpp:37:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

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