제출 #418056

#제출 시각아이디문제언어결과실행 시간메모리
418056ChaskaCollecting Stamps 3 (JOI20_ho_t3)C++11
5 / 100
1 ms588 KiB
#include <bits/stdc++.h>
#define F first
#define S second
#define ll long long
using namespace std;
typedef pair<long long,long long> ii;
typedef pair<int,ii> i3;

const int N = 15+5;
int n,l;
int a[N],b[N],res;
int dp[N][N][205];
bool vs[N][N][205];
int dfs(int u,int v,int ti)
{
    if (ti>200) return 0;
    if (u>v) return 0;
    if (vs[u][v][ti]) return dp[u][v][ti];
    vs[u][v][ti] = true;
    for (int i=u+1;i<=v+1;i++) {
        int k = 0;
        for (int j=u;j<i;j++) if (a[j]+ti<=b[j]) k++;
        dp[u][v][ti] = max(dp[u][v][ti],dp[i][v][ti+a[i-1]+a[i-1]]+k);
        dp[u][v][ti] = max(dp[u][v][ti],dfs(i,v,ti+a[i-1]+a[i-1])+k);
    }
    for (int i=v-1;i>=u-1;i--) {
        int k = 0;
        for (int j=v;j>i;j--) if (l-a[j]+ti<=b[j]) k++;
        dp[u][v][ti] = max(dp[u][v][ti],dfs(u,i,ti+l-a[i+1]+l-a[i+1])+k);
    }
    return dp[u][v][ti];
}
int main()
{
    cin.tie(0); ios_base::sync_with_stdio(0);
    cin >> n >> l;
    
    for (int i=0;i<n;i++) cin >> a[i];
    for (int i=0;i<n;i++) cin >> b[i];
    for (int i=0;i<n;i++) if (a[i]<=b[i]) res++;
    int k = 0;
    for (int i=0;i<n;i++) if (l-a[i]<=b[i]) k++;
    res = max(res,k);
    cout << max(res,dfs(0,n-1,0));
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...