Submission #996905

#	Time	Username	Problem	Language	Result	Execution time	Memory
996905		irmuun	Collecting Stamps 3 (JOI20_ho_t3)	C++17	5 / 100	2749 ms	1048584 KiB

ho_t3

#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()

//try
template<class T> T &chmax(T &a,const T &b){ return a = max(a,b); }

int main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    ll n,L;
    cin>>n>>L;
    ll x[n+5],t[n+5];
    for(ll i=1;i<=n;i++){
        cin>>x[i];
    }
    for(ll i=1;i<=n;i++){
        cin>>t[i];
    }
    x[0]=0;
    function <ll(ll,ll)> dist=[&](ll a,ll b){
        return min(abs(x[a]-x[b]),L-abs(x[a]-x[b]));
    };
    ll dp[1<<n][n+5][405];
    memset(dp,-1,sizeof dp);
    dp[0][0][0]=0;
    for(ll s=0;s<(1<<n);s++){
        for(ll i=0;i<=n;i++){
            if(i==0||(s&(1<<(i-1)))){
                for(ll T=0;T<=200;T++){
                    if(dp[s][i][T]==-1) continue;
                    for(ll j=0;j<n;j++){//next pos
                        if((s&(1<<j))==0){//currently not stamped j
                            chmax(dp[s|(1<<j)][j+1][T+dist(i,j+1)],dp[s][i][T]+(T+dist(i,j+1)<=t[j+1]));
                        }
                    }
                }
            }
        }
    }
    ll ans=0;
    for(ll s=0;s<(1<<n);s++){
        for(ll i=1;i<=n;i++){
            for(ll T=0;T<=200;T++){
                ans=max(ans,dp[s][i][T]);
            }
        }
    }
    cout<<ans;
}

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