Submission #218106

#	Time	Username	Problem	Language	Result	Execution time	Memory
218106		PeppaPig	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	142 ms	131576 KiB

ho_t3

#include <bits/stdc++.h>

#define long long long

using namespace std;

const int N = 205;


int n, l, ans;
int x[N], t[N];
long L[N][N][N], R[N][N][N];

long d(int a, int b) { return min(abs(x[b] - x[a]), l - abs(x[b] - x[a])); }

int main() {
    scanf("%d %d", &n, &l);
    for(int i = 1; i <= n; i++) scanf("%d", x + i); 
    for(int i = 1; i <= n; i++) scanf("%d", t + i); 
    x[n + 1] = l;

    for(int k = 0; k <= n; k++) for(int i = 0; i <= n; i++) for(int j = n + 1; j; j--) {
        if(j <= i || (!i && j == n + 1 && !k)) continue;
        L[k][i][j] = R[k][i][j] = 1e18;

        if(i) L[k][i][j] = min({L[k][i][j], L[k][i-1][j] + d(i-1, i), R[k][i-1][j] + d(i, j)});
        if(j <= n) R[k][i][j] = min({R[k][i][j], L[k][i][j+1] + d(i, j), R[k][i][j+1] + d(j+1, j)});

        if(k) {
            if(i) {
                long T = min(L[k-1][i-1][j] + d(i-1, i), R[k-1][i-1][j] + d(j, i));
                if(T <= t[i]) L[k][i][j] = min(L[k][i][j], T);
            }
            if(j <= n) {
                long T = min(L[k-1][i][j+1] + d(i, j), R[k-1][i][j+1] + d(j+1, j));
                if(T <= t[j]) R[k][i][j] = min(R[k][i][j], T);
            }
        }
        if(L[k][i][j] != 1e18 || R[k][i][j] != 1e18)
            ans = max(ans, k);
    }
    printf("%d\n", ans);

    return 0;
}

Compilation message (stderr)

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:17: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:18:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= n; i++) scanf("%d", x + i); 
                                 ~~~~~^~~~~~~~~~~~~
ho_t3.cpp:19:38: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     for(int i = 1; i <= n; i++) scanf("%d", t + i); 
                                 ~~~~~^~~~~~~~~~~~~

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