Submission #203643

#	Time	Username	Problem	Language	Result	Execution time	Memory
203643		osaaateiasavtnl	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	139 ms	139384 KiB

ho_t3

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
#define Time (double)clock()/CLOCKS_PER_SEC
const int N = 207, INF = 1e9 + 7;
int dp[N][N][N][2];
int n, L, x[N], t[N];
void upd(int &a, int b) { a = min(a, b); }
signed main() {
    #ifdef HOME
    freopen("input.txt", "r", stdin);
    #else
    ios_base::sync_with_stdio(0); cin.tie(0);
    #endif
    cin >> n >> L;
    for (int i = 1; i <= n; ++i)
        cin >> x[i];
    for (int i = 1; i <= n; ++i)
        cin >> t[i];
    for (int i = 0; i < N; ++i)
        for (int j = 0; j < N; ++j)
            for (int k = 0; k < N; ++k)
                for (int t = 0; t < 2; ++t)
                    dp[i][j][k][t] = INF;
 
    x[0] = 0;
    x[n + 1] = L;
    n += 2;
 
    dp[0][0][n][0] = dp[0][0][n][1] = 0;
 
    /*
    for (int i = 0; i < n; ++i)
        cout << x[i] << ' ';
    cout << '\n';
    */
 
    dp[0][0][n - 1][0] = dp[0][0][n - 1][0] = 0;
    for (int i = 0; i + 1 < N; ++i) {
        for (int l = 0; l < n - 1; ++l) {
            for (int r = n - 1; r; --r) {
                int tt;
 
                if (r - l <= 1)
                    continue;
 
                if (dp[i][l][r][0] < INF) {
                    tt = dp[i][l][r][0] + x[l + 1] - x[l];
                    upd(dp[i + (tt <= t[l + 1])][l + 1][r][0], tt);
 
                    tt = dp[i][l][r][0] + x[l] + (L - x[r - 1]);
                    upd(dp[i + (tt <= t[r - 1])][l][r - 1][1], tt);                
                }
 
                if (dp[i][l][r][1] < INF) {
                    tt = dp[i][l][r][1] + (L - x[r]) + x[l + 1];
                    upd(dp[i + (tt <= t[l + 1])][l + 1][r][0], tt);
 
                    tt = dp[i][l][r][1] + x[r] - x[r - 1];
                    upd(dp[i + (tt <= t[r - 1])][l][r - 1][1], tt);
                }
            }   
        }   
    }   
    for (int i = N - 1; ; --i) {
        for (int l = 0; l < N; ++l) 
            for (int r = 0; r < N; ++r)
                for (int t = 0; t < 2; ++t)
                    if (dp[i][l][r][t] < INF) {
                        cout << i << '\n';
                        exit(0);
                    }   
    }   
}

Compilation message (stderr)

ho_t3.cpp: In function 'int main()':
ho_t3.cpp:46:24: warning: operation on 'dp[0][0][(n - 1)][0]' may be undefined [-Wsequence-point]
     dp[0][0][n - 1][0] = dp[0][0][n - 1][0] = 0;
     ~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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