Submission #418056

#	Time	Username	Problem	Language	Result	Execution time	Memory
418056		Chaska	Collecting Stamps 3 (JOI20_ho_t3)	C++11	5 / 100	1 ms	588 KiB

ho_t3

#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;
}

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