제출 #1131004

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1131004		ByeWorld	Collecting Stamps 3 (JOI20_ho_t3)	C++20	100 / 100	226 ms	202404 KiB

ho_t3

#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define int long long
#define ll long long
#define pb push_back
#define fi first
#define se second
#define lf (id<<1)
#define rg ((id<<1)|1)
#define md ((l+r)>>1)
#define ld long double
using namespace std;
typedef pair<int,int> pii;
typedef pair<char,char> pcc;
typedef pair<int,pii> ipii;
typedef pair<pii,pii> ipiii;
const int MAXN = 1e5+10;
const int MAXA = 1e6;
const int INF = 1e18+10;
const int MOD = 1e9+7;
const int LOG = 21;
const ld EPS = 1e-12;
void chmx(int &a, int b){ a = max(a, b); }
void chmn(int &a, int b){ a = min(a, b); }

int n, l;
int x[210], t[210];
int dp[210][210][210][3];

signed main(){
    // ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> l;
    for(int i=1; i<=n; i++) cin >> x[i];
    for(int i=1; i<=n; i++) cin >> t[i];
    x[n+1] = l;

    for(int i=0; i<=n+1; i++)
        for(int j=0; j<=n+1; j++)
            for(int k=0; k<=n; k++) 
                dp[i][j][k][0] = INF, dp[i][j][k][1] = INF;
    dp[0][n+1][0][0] = dp[0][n+1][0][1] = 0;
    
    int ans = 0;
    for(int k=0; k<=n; k++){
        for(int i=0; i<=n; i++){
            for(int j=n+1; j>=i+1; j--){
                if(k==0 && i==0 && j==n+1) continue;

                if(i!=0){
                    int dis = x[i]-x[i-1];
                    chmn(dp[i][j][k][0], dp[i-1][j][k][0]+dis);
                    if(dp[i-1][j][k-1][0]+dis <= t[i] && k!=0)
                        chmn(dp[i][j][k][0], dp[i-1][j][k-1][0]+dis);

                    dis = (x[i] + l-x[j]);
                    chmn(dp[i][j][k][0], dp[i-1][j][k][1]+dis);
                    if(dp[i-1][j][k-1][1]+dis <= t[i] && k!=0)
                        chmn(dp[i][j][k][0], dp[i-1][j][k-1][1]+dis);
                }
                if(j!=n+1){
                    int dis = x[j+1]-x[j];
                    chmn(dp[i][j][k][1], dp[i][j+1][k][1]+dis);
                    if(dp[i][j+1][k-1][1]+dis <= t[j] && k!=0)
                        chmn(dp[i][j][k][1], dp[i][j+1][k-1][1]+dis);

                    dis = (l-x[j] + x[i]);
                    chmn(dp[i][j][k][1], dp[i][j+1][k][0]+dis);
                    if(dp[i][j+1][k-1][0]+dis <= t[j] && k!=0)
                        chmn(dp[i][j][k][1], dp[i][j+1][k-1][0]+dis);
                }
                if(dp[i][j][k][0] != INF) chmx(ans, k);
                if(dp[i][j][k][1] != INF) chmx(ans, k);
            }
        }
    }
    // cout << dp[0][4][7][1] << " pp\n";
    cout << ans << '\n';
} 

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