Submission #233714

#	Time	Username	Problem	Language	Result	Execution time	Memory
233714		duality	Collecting Stamps 3 (JOI20_ho_t3)	C++11	100 / 100	356 ms	127640 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pb push_back
typedef long long int LLI;
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vpii;

int N,L,X[200],T[200];
LLI dp[201][201][201][2];
LLI findAns(int a,int b,int s,int c) {
    if (s < 0) return 1e18;
    else if ((a == 0) && (b == 0)) return (s == 0) ? 0:1e18;
    else if ((c == 0) && (a == 0)) return 1e18;
    else if ((c == 1) && (b == 0)) return 1e18;
    else if (dp[a][b][s][c] != -1) return dp[a][b][s][c];
    LLI ans = 1e18;
    if (c == 0) {
        ans = min(ans,findAns(a-1,b,s,0)+X[a-1]-((a == 1) ? 0:X[a-2]));
        LLI x = findAns(a-1,b,s-1,0)+X[a-1]-((a == 1) ? 0:X[a-2]);
        if (x <= T[a-1]) ans = min(ans,x);
        if (b > 0) {
            ans = min(ans,findAns(a-1,b,s,1)+X[a-1]+L-X[N-b]);
            LLI x = findAns(a-1,b,s-1,1)+X[a-1]+L-X[N-b];
            if (x <= T[a-1]) ans = min(ans,x);
        }
    }
    else {
        ans = min(ans,findAns(a,b-1,s,1)+((b == 1) ? L:X[N-b+1])-X[N-b]);
        LLI x = findAns(a,b-1,s-1,1)+((b == 1) ? L:X[N-b+1])-X[N-b];
        if (x <= T[N-b]) ans = min(ans,x);
        if (a > 0) {
            ans = min(ans,findAns(a,b-1,s,0)+X[a-1]+L-X[N-b]);
            LLI x = findAns(a,b-1,s-1,0)+X[a-1]+L-X[N-b];
            if (x <= T[N-b]) ans = min(ans,x);
        }
    }
    dp[a][b][s][c] = ans;
    return ans;
}
int main() {
    int i,j;
    scanf("%d %d",&N,&L);
    for (i = 0; i < N; i++) scanf("%d",&X[i]);
    for (i = 0; i < N; i++) scanf("%d",&T[i]);
    memset(dp,-1,sizeof(dp));
    for (i = N; i >= 0; i--) {
        for (j = 0; j <= N; j++) {
            if (findAns(j,N-j,i,0) < 1e18) break;
            if (findAns(j,N-j,i,1) < 1e18) break;
        }
        if (j <= N) break;
    }
    printf("%d\n",i);

    return 0;
}

Compilation message (stderr)

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:44: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:45:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (i = 0; i < N; i++) scanf("%d",&X[i]);
                             ~~~~~^~~~~~~~~~~~
ho_t3.cpp:46:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for (i = 0; i < N; i++) scanf("%d",&T[i]);
                             ~~~~~^~~~~~~~~~~~

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