제출 #1130732

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1130732		ByeWorld	Collecting Stamps 3 (JOI20_ho_t3)	C++20	15 / 100	224 ms	200416 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); }


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<=200; 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=1; k<=200; k++){
        for(int i=0; i<=n; i++){
            for(int j=i+1; j<=n+1; j++){
                if(i!=0){
                    int val = (k<=t[i]);
                    int oth = k - (x[i]-x[i-1]);
                    if(oth>=0)
                        chmx(dp[i][j][k][0], dp[i-1][j][oth][0]+val);

                    oth = k - (x[i] + l-x[j]);
                    if(oth>=0)
                        chmx(dp[i][j][k][0], dp[i-1][j][oth][1]+val);
                }
                if(j!=n+1){
                    int val = (k<=t[j]);
                    int oth = k - (x[j+1]-x[j]);
                    if(oth>=0)
                        chmx(dp[i][j][k][1], dp[i][j+1][oth][1]+val);

                    oth = k - (l-x[j] + x[i]);
                    if(oth>=0)
                        chmx(dp[i][j][k][1], dp[i][j+1][oth][0]+val);
                }
                chmx(ans, max(dp[i][j][k][0], dp[i][j][k][1]) );
            }
        }
    }
    // cout << dp[0][4][7][1] << " pp\n";
    cout << ans << '\n';
} 

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