Submission #224045

#	Time	Username	Problem	Language	Result	Execution time	Memory
224045		tqbfjotld	Collecting Stamps 3 (JOI20_ho_t3)	C++14	15 / 100	232 ms	135288 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 1000000000000000000LL
#define DEBUG false

int pos[205];
int reqt[205];
bool collected[205];
int n,L;
int memo[205][205][205][2];

int func(int l, int r, int num, bool side){
    if (l==0 && r==0){
        return num==0?0:INF;
    }
    if (l==0){
        if (!side) return memo[l][r][num][side] = INF;
    }
    if (r==0){
        if (side) return memo[l][r][num][side] = INF;
    }
    if (num<=0){
        return side?pos[r-1]:(L-pos[n-l]);
    }
    if (memo[l][r][num][side]!=-1) return memo[l][r][num][side];


    if (side){
        int ans = INF;
        ans = min(ans,func(l,r-1,num,true)+pos[r-1]-pos[r-2]);
        if (DEBUG) printf("%d %d\n",ans,func(l,r-1,num,true));
        ans = min(ans,func(l,r-1,num,false)+pos[r-1]+L-pos[n-l]);
        if (DEBUG) printf("%d\n",ans);
        int t = func(l,r-1,num-1,true);
        if (t+pos[r-1]-pos[r-2]<=reqt[r-1]){
            ans = min(ans,t+pos[r-1]-pos[r-2]);
        }
        if (DEBUG) printf("%d\n",ans);
        t = func(l,r-1,num-1,false);
        if (t+pos[r-1]+L-pos[n-l]<=reqt[r-1]){
            ans = min(ans,t+pos[r-1]+L-pos[n-1]);
        }
        if (DEBUG) printf("%d\n",ans);
        return memo[l][r][num][side] = ans;
    }
    else{
        int ans = INF;
        ans = min(ans,func(l-1,r,num,true)+pos[r-1]+L-pos[n-l]);
        ans = min(ans,func(l-1,r,num,false)+pos[n-l+1]-pos[n-l]);
        int t = func(l-1,r,num-1,true);
        if (t+pos[r-1]+L-pos[n-l]<=reqt[n-l]){
            ans = min(ans,t+pos[r-1]+L-pos[n-l]);
        }
        t = func(l-1,r,num-1,false);
        if (t+pos[n-l+1]-pos[n-l]<=reqt[n-l]){
            ans = min(ans,t+pos[n-l+1]-pos[n-l]);
        }
        return memo[l][r][num][side] = ans;
    }
}

main(){
    scanf("%lld%lld",&n,&L);
    for (int x = 0; x<n; x++){
        scanf("%lld",&pos[x]);
    }
    for (int x = 0; x<n; x++){
        scanf("%lld",&reqt[x]);
    }
    pos[n] = L;
    reqt[n] = INF;
    memset(memo,-1,sizeof(memo));
    int ans = 0;
    for (int x = 0; x<=n; x++){
        for (int t = 0; t<=n; t++){
             //   printf("time for %d to %d, %d stamps, end at right = %d\n",-x,n-x,t,func(x,n-x,t,true));
            if (func(x,n-x,t,true)<INF){

                ans = max(ans,t);
            }
            if (func(x,n-x,t,false)<INF){
                ans = max(ans,t);
            }
        }
    }
    printf("%lld",ans);
}

Compilation message (stderr)

ho_t3.cpp: In function 'long long int func(long long int, long long int, long long int, bool)':
ho_t3.cpp:32:61: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
         if (DEBUG) printf("%d %d\n",ans,func(l,r-1,num,true));
                                                             ^
ho_t3.cpp:32:61: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
ho_t3.cpp:34:37: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
         if (DEBUG) printf("%d\n",ans);
                                     ^
ho_t3.cpp:39:37: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
         if (DEBUG) printf("%d\n",ans);
                                     ^
ho_t3.cpp:44:37: warning: format '%d' expects argument of type 'int', but argument 2 has type 'long long int' [-Wformat=]
         if (DEBUG) printf("%d\n",ans);
                                     ^
ho_t3.cpp: At global scope:
ho_t3.cpp:63:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
ho_t3.cpp: In function 'int main()':
ho_t3.cpp:64:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld%lld",&n,&L);
     ~~~~~^~~~~~~~~~~~~~~~~~
ho_t3.cpp:66:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&pos[x]);
         ~~~~~^~~~~~~~~~~~~~~~
ho_t3.cpp:69:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld",&reqt[x]);
         ~~~~~^~~~~~~~~~~~~~~~~

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