제출 #224046

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
224046		tqbfjotld	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	321 ms	135308 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];
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-l]);
        }
        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);
}

컴파일 시 표준 에러 (stderr) 메시지

ho_t3.cpp: In function 'long long int func(long long int, long long int, long long int, bool)':
ho_t3.cpp:31: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:31:61: warning: format '%d' expects argument of type 'int', but argument 3 has type 'long long int' [-Wformat=]
ho_t3.cpp:33: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:38: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:43: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:62:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
ho_t3.cpp: In function 'int main()':
ho_t3.cpp:63: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:65: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:68: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: 10 / 10
• Subtask 4: 75 / 75