Submission #647332

#	Time	Username	Problem	Language	Result	Execution time	Memory
647332		ck_platypus	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	94 ms	127544 KiB

ho_t3

#include <iostream>
#include <string>
#include <cmath>
#include <vector>
#include <algorithm>
#include <utility>
#include <bitset>
#include <climits>
#include <set>
#include <map>
#include <iomanip>
#include <queue>
#include <cstring>
#include <fstream>
using namespace std;
#define ll long long
#define pb push_back
#define mp make_pair
#define pll pair<ll, ll>
#define plpll pair<ll, pll>
#define pii pair<int, int>
#define f first
#define s second
#define inf 1000000000000
#define endl '\n'
ll dp[201][201][201][2];
 
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    for(int i=0;i<201;i++) for(int j=0;j<201;j++) for(int k=0;k<201;k++) dp[i][j][k][0]=dp[i][j][k][1]=inf;
    ll n, L;
    int aans=0;
    cin >> n >> L;
    ll x[n], t[n];
    for(int i=0;i<n;i++) cin >> x[i];
    for(int i=0;i<n;i++) cin >> t[i];
    dp[0][0][0][0]=dp[0][0][0][1]=0;
    dp[0][1][0][1]=x[0];
    dp[0][1][0][0]=2*x[0];
    if(x[0]<=t[0]){
        dp[0][1][1][1]=x[0];
        dp[0][1][1][0]=2*x[0];
    }
    for(int r=2;r<=n;r++){
        dp[0][r][0][1]=x[r-1];
        dp[0][r][0][0]=2*x[r-1];
        for(int ans=1;ans<=r;ans++){
            if(dp[0][r-1][ans-1][1]+x[r-1]-x[r-2]<=t[r-1]) dp[0][r][ans][1]=dp[0][r-1][ans-1][1]+x[r-1]-x[r-2];
            else dp[0][r][ans][1]=dp[0][r-1][ans][1]+x[r-1]-x[r-2];
            dp[0][r][ans][0]=dp[0][r][ans][1]+x[r-1];
        }
    }
    for(int l=1;l<=n;l++){
        dp[l][0][0][0]=L-x[n-l];
        dp[l][0][0][1]=2*(L-x[n-l]);
        for(int ans=1;ans<=l;ans++){
            if(l==1){
                if(L-x[n-1]<=t[n-1]) dp[1][0][1][0]=L-x[n-1];
            }else{
                if(dp[l-1][0][ans-1][0]+x[n-l+1]-x[n-l]<=t[n-l]) dp[l][0][ans][0]=dp[l-1][0][ans-1][0]+x[n-l+1]-x[n-l];
                else dp[l][0][ans][0]=dp[l-1][0][ans][0]+x[n-l+1]-x[n-l];
            }
            dp[l][0][ans][1]=dp[l][0][ans][0]+L-x[n-l];
        }
        for(int r=1;l+r<=n;r++){
            for(int ans=1;ans<=l+r;ans++){
                if(l==1){
                    if(dp[l-1][r][ans-1][0]+L-x[n-l]<=t[n-l]) dp[l][r][ans][0]=dp[l-1][r][ans-1][0]+L-x[n-l];
                    else dp[l][r][ans][0]=dp[l-1][r][ans][0]+L-x[n-l];
                }else{
                    if(dp[l-1][r][ans-1][0]+x[n-l+1]-x[n-l]<=t[n-l]) dp[l][r][ans][0]=dp[l-1][r][ans-1][0]+x[n-l+1]-x[n-l];
                    else dp[l][r][ans][0]=dp[l-1][r][ans][0]+x[n-l+1]-x[n-l];
                }
                if(r==1){
                    if(dp[l][r-1][ans-1][1]+x[r-1]<=t[r-1]) dp[l][r][ans][1]=dp[l][r-1][ans-1][1]+x[r-1];
                    else dp[l][r][ans][1]=dp[l][r-1][ans][1]+x[r-1];
                }else{
                    if(dp[l][r-1][ans-1][1]+x[r-1]-x[r-2]<=t[r-1]) dp[l][r][ans][1]=dp[l][r-1][ans-1][1]+x[r-1]-x[r-2];
                    else dp[l][r][ans][1]=dp[l][r-1][ans][1]+x[r-1]-x[r-2];
                }
                dp[l][r][ans][0]=min(dp[l][r][ans][0], dp[l][r][ans][1]+x[r-1]+L-x[n-l]);
                dp[l][r][ans][1]=min(dp[l][r][ans][1], dp[l][r][ans][0]+x[r-1]+L-x[n-l]);
            }
        }
    }
    for(int i=0;i<201;i++)
        for(int j=0;j<201;j++)
            for(int k=0;k<201;k++)
                if(dp[i][j][k][0]<inf || dp[i][j][k][1]<inf) aans=max(aans, k);
    cout << aans << endl;
    /*ll a, b;
    while(cin >> a >> b){
        for(int i=1;i<=a+b;i++) cout << dp[a][b][i][0] << " ";cout << endl;
        for(int i=1;i<=a+b;i++) cout << dp[a][b][i][1] << " ";cout << endl;
    }*/
    return 0;
}

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