제출 #1370698

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1370698		Born_To_Laugh	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	69 ms	134036 KiB

ho_t3

// Born_To_Laugh - Hughie Do
#include <bits/stdc++.h>
#define alle(AC) AC.begin(), AC.end()
#define fi first
#define se second
using namespace std;
typedef long long ll;
[[maybe_unused]] const int MOD = 998244353, INF = 3e18 + 7;

const int maxn = 210;
int n, l;
ll dp[maxn][maxn][maxn][2];
int xx[maxn], t[maxn];

void solve(){
    cin >> n >> l;
    for(int i=1; i<=n; ++i) cin >> xx[i];
    for(int i=1; i<=n; ++i) cin >> t[i];
    xx[n + 1] = l;

    for(int i=0; i<=n; ++i){
        for(int j=0; j<=n; ++j){
            for(int k=0; k<=n; ++k){
                dp[i][j][k][0] = dp[i][j][k][1] = INF;
            }
        }
    }

    dp[0][0][0][0] = dp[0][0][0][1] = 0;
    for(int i=0; i<=n; ++i){
        for(int j=0; j<n - i; ++j){
            for(int x=0; x<n; ++x){
                if(dp[i][j][x][0] != INF){
                    ll ti = xx[n - i + 1] - xx[n - i];
                    if(dp[i][j][x][0] + ti <= t[n - i]){
                        dp[i + 1][j][x + 1][0] = min(dp[i + 1][j][x + 1][0], dp[i][j][x][0] + ti);
                    }
                    else dp[i + 1][j][x][0] = min(dp[i + 1][j][x][0], dp[i][j][x][0] + ti);

                    ti = l - xx[n - i + 1] + xx[j + 1];
                    if(dp[i][j][x][0] + ti <= t[j + 1]){
                        dp[i][j + 1][x + 1][1] = min(dp[i][j + 1][x + 1][1], dp[i][j][x][0] + ti);
                    }
                    else dp[i][j + 1][x][1] = min(dp[i][j + 1][x][1], dp[i][j][x][0] + ti);
                }
                if(dp[i][j][x][1] != INF){
                    ll ti = xx[j + 1] - xx[j];
                    if(dp[i][j][x][1] + ti <= t[j + 1]){
                        dp[i][j + 1][x + 1][1] = min(dp[i][j + 1][x + 1][1], dp[i][j][x][1] + ti);
                    }
                    else dp[i][j + 1][x][1] = min(dp[i][j + 1][x][1], dp[i][j][x][1] + ti);

                    ti = l - xx[n - i] + xx[j];
                    if(dp[i][j][x][1] + ti <= t[n - i]){
                        dp[i + 1][j][x + 1][0] = min(dp[i + 1][j][x + 1][0], dp[i][j][x][1] + ti);
                    }
                    else dp[i + 1][j][x][0] = min(dp[i + 1][j][x][0], dp[i][j][x][1] + ti);
                }
            }
        }
    }

    int ans = 0;
    for(int i=0; i<=n; ++i){
        for(int j=0; j<=n; ++j){
            for(int x=0; x<=n; ++x){
                if(dp[i][j][x][0] != INF || dp[i][j][x][1] != INF){
                    ans = max(ans, x);
                    // cout << i << ' ' << j << ' ' << x << ' ' << dp[i][j][x][0] << ' ' << dp[i][j][x][1] << '\n';
                }
            }
        }
    }
    cout << ans << '\n';
}
signed main(){
    // freopen("inp.txt", "r", stdin);
    // freopen("out.txt", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    solve();
}

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

ho_t3.cpp:8:56: warning: overflow in conversion from 'double' to 'int' changes value from '3.0e+18' to '2147483647' [-Woverflow]
    8 | [[maybe_unused]] const int MOD = 998244353, INF = 3e18 + 7;
      |                                                   ~~~~~^~~

• 서브태스크 1: 5 / 5
• 서브태스크 2: 10 / 10
• 서브태스크 3: 10 / 10
• 서브태스크 4: 75 / 75