Submission #1309917

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309917		StefanSebez	Collecting Stamps 3 (JOI20_ho_t3)	C++20	100 / 100	274 ms	522200 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
#define ld long double
const int N=205;
const ll INF=1e18;
void chmn(ll &x,ll y){x=min(x,y);}
int n;ll L;
ll X[2*N],T[2*N];
ll dp[2][2*N][2*N][N];
ll dist(int i,int j){
    return min(abs(X[i]-X[j]),L-abs(X[i]-X[j]));
}
int main(){
    scanf("%i%lld",&n,&L);
    for(int i=1;i<=n;i++) scanf("%lld",&X[i]);
    for(int i=1;i<=n;i++) scanf("%lld",&T[i]);
    n++;T[0]=-1;
    for(int i=n;i<2*n;i++)X[i]=X[i-n],T[i]=T[i-n];
    for(int l=0;l<2*n;l++){
        for(int r=0;r<2*n;r++){
            for(int k=0;k<=n;k++){
                dp[0][l][r][k]=dp[1][l][r][k]=INF;
            }
        }
    }
    dp[0][n][n][0]=dp[1][n][n][0]=0;
    int res=0;
    for(int l=n;l>=0;l--){
        for(int r=n;r<=n+l-1;r++){
            for(int k=0;k<=n;k++){
                chmn(dp[0][l][r][k],dp[0][l+1][r][k]+dist(l,l+1));
                if(k>0&&dp[0][l+1][r][k-1]+dist(l,l+1)<=T[l])chmn(dp[0][l][r][k],dp[0][l+1][r][k-1]+dist(l,l+1));
                chmn(dp[0][l][r][k],dp[1][l+1][r][k]+dist(l,r));
                if(k>0&&dp[1][l+1][r][k-1]+dist(l,r)<=T[l])chmn(dp[0][l][r][k],dp[1][l+1][r][k-1]+dist(l,r));
                if(dp[0][l][r][k]<INF)res=max(res,k);
                chmn(dp[1][l][r][k],dp[0][l][r-1][k]+dist(r,l));
                if(k>0&&dp[0][l][r-1][k-1]+dist(r,l)<=T[r])chmn(dp[1][l][r][k],dp[0][l][r-1][k-1]+dist(r,l));
                chmn(dp[1][l][r][k],dp[1][l][r-1][k]+dist(r,r-1));
                if(k>0&&dp[1][l][r-1][k-1]+dist(r,r-1)<=T[r])chmn(dp[1][l][r][k],dp[1][l][r-1][k-1]+dist(r,r-1));
                if(dp[1][l][r][k]<INF)res=max(res,k);
            }
        }
    }
    printf("%i\n",res);
    return 0;
}

Compilation message (stderr)

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:18:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   18 |     scanf("%i%lld",&n,&L);
      |     ~~~~~^~~~~~~~~~~~~~~~
ho_t3.cpp:19:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     for(int i=1;i<=n;i++) scanf("%lld",&X[i]);
      |                           ~~~~~^~~~~~~~~~~~~~
ho_t3.cpp:20:32: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |     for(int i=1;i<=n;i++) scanf("%lld",&T[i]);
      |                           ~~~~~^~~~~~~~~~~~~~

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