Submission #996926

#	Time	Username	Problem	Language	Result	Execution time	Memory
996926		irmuun	Collecting Stamps 3 (JOI20_ho_t3)	C++17	15 / 100	521 ms	1048576 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); }
template<class T> T &chmin(T &a,const T &b){ return a = min(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][n+5];
    for(ll i=0;i<(1<<n);i++){
        for(ll j=0;j<=n;j++){
            for(ll k=0;k<=n;k++){
                dp[i][j][k]=1e18;
            }
        }
    }
    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 k=0;k<=n;k++){
                    if(dp[s][i][k]==1e18) continue;
                    for(ll j=0;j<n;j++){//next pos 0-indexed
                        if((s&(1<<j))==0){//currently not stamped j
                            chmin(dp[s|(1<<j)][j+1][k+(dp[s][i][k]+dist(i,j+1)<=t[j+1])],dp[s][i][k]+dist(i,j+1));
                        }
                    }
                }
            }
        }
    }
    ll ans=0;
    for(ll s=0;s<(1<<n);s++){
        for(ll i=0;i<=n;i++){
            for(ll k=0;k<=n;k++){
                if(dp[s][i][k]!=1e18){
                    ans=max(ans,k);
                }
            }
        }
    }
    cout<<ans;
}

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