Submission #224204

#	Time	Username	Problem	Language	Result	Execution time	Memory
224204		dantoh000	Collecting Stamps 3 (JOI20_ho_t3)	C++14	0 / 100	69 ms	135288 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef long long ll;
const ll INF = 1000000000000000000;
int n,l;
int p[205], t[205];
ll mem[2][205][205][205];
///min time to reach state:
///[0,x[i]] U [x[j],L] visited;
///at x[i]/ x[j] depends on d
///k stamps collect;
ll dp(int d, int i, int j, int k){
    if (mem[d][i][j][k] != -1) return mem[d][i][j][k];
    ll res = INF;
    ///try not taking anything
    if (d == 0 && i != 0){
        res = min(dp(0,i-1,j,k)+p[i]-p[i-1],
                  dp(1,i-1,j,k)+l-p[j]+p[i-1]);
    }
    if (d == 1 && j != n+1){
        res = min(dp(0,i,j+1,k)+l-p[j]+p[i],
                  dp(1,i,j+1,k)+p[j+1]-p[j]);
    }
    if (k){
        ll T = INF;
        if (d == 0 && i != 0){
            T = dp(0,i-1,j,k-1)+p[i]-p[i-1];
            //printf("if from %d to %d clock, take %lld+%d\n",i-1,i,dp(0,i-1,j,k-1),p[i]-p[i-1]);
            if (T <= t[i]) res = min(res,T);
            T = dp(1,i-1,j,k-1)+l-p[j]+p[i];
            //printf("if from %d to %d clock, take %lld+%d\n",j,i,dp(1,i-1,j,k-1),l-p[j]+p[i]);
            if (T <= t[i]) res = min(res,T);
        }
        if (d == 1 && j != n+1){
            T = dp(0,i,j+1,k-1)+l-p[j]+p[i];
            //printf("if from %d to %d anticlock, take %lld+%d\n",i,j,dp(0,i,j+1,k-1),l-p[j]+p[i]);
            if (T <= t[j]) res = min(res,T);
            T = dp(1,i,j+1,k-1)+p[j+1]-p[j];
            //printf("if from %d to %d anticlock, take %lld+%d\n",j+1,j,dp(1,i,j+1,k-1),p[j+1]-p[j]);
            if (T <= t[j]) res = min(res,T);
        }
    }
    //printf("%d %d %d %d %lld\n",d,i,j,k,res);
    return mem[d][i][j][k] = res;
}
int main(){
    scanf("%d%d",&n,&l);
    for (int i = 1; i <= n; i++){
        scanf("%d",&p[i]);
    }
    p[n+1] = l;
    for (int i = 1; i <= n; i++){
        scanf("%d",&t[i]);
    }
    t[0] = t[n+1] = 0;
    memset(mem,-1,sizeof(mem));
    mem[0][0][n+1][0] = mem[1][0][n+1][0] = 0;
    int ans = 0;
    for (int i = 0; i <= n; i++){
        for (int j = 0; j <= n; j++){
            if (dp(0,i,i+1,j) < INF || dp(1,i,i+1,j) < INF) {
                //printf("%d %d %d\n",i,i+1,j);
                ans = max(ans,j);
            }
        }
    }
    printf("%d ",ans);



}

Compilation message (stderr)

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:48: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:50:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&p[i]);
         ~~~~~^~~~~~~~~~~~
ho_t3.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d",&t[i]);
         ~~~~~^~~~~~~~~~~~

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