Submission #638888

#	Time	Username	Problem	Language	Result	Execution time	Memory
638888		new_acc	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	85 ms	135256 KiB

ho_t3

#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef vector<int> vi;
typedef vector<ll> vl;
const int N=2e2+10;
const int SS=1<<19;
const int INFi=2e9;
const ll INFl=1e16;
const ll mod2=998244353;
const ll mod=1e9+7;
const ll mod3=1000696969;
const ll p=70032301;
const ull p2=913;
const int L=20;
ll t1[N],t2[N],n,dp[N][N][2][N],xd;
void solve(){
    cin>>n>>xd;
    for(int i=1;i<=n;i++) cin>>t1[i];
    for(int i=1;i<=n;i++) cin>>t2[i];
    for(int i=0;i<=n+1;i++){
        for(int i2=0;i2<=n+1;i2++){
            for(int i3=0;i3<2;i3++){
                for(int i4=1;i4<=n+1;i4++) dp[i][i2][i3][i4]=-1;
                dp[i][i2][i3][0]=INFl;
            }
        }
    }
    for(int i=n;i>=0;i--){
        for(int i2=n-i;i2>=0;i2--){
            for(int i3=0;i3<2;i3++){
                for(int i4=1;i4<=n-(i+i2)+1;i4++){
                    if(!i3 and i==0) continue;
                    if(i3 and i2==0) continue;
                    if(i+i2==n){
                        if(!i3) dp[i][i2][i3][i4]=t2[i]; 
                        else dp[i][i2][i3][i4]=t2[n-i2+1];
                        continue;
                    }
                    if(!i3){
                        dp[i][i2][i3][i4]=max({dp[i][i2][i3][i4],
                            min(dp[i+1][i2][i3][i4-1]-(t1[i+1]-t1[i]),t2[i]),
                            dp[i+1][i2][i3][i4]-(t1[i+1]-t1[i]),
                            min(dp[i][i2+1][1][i4-1]-(t1[i]+xd-t1[n-i2]),t2[i]),
                            dp[i][i2+1][1][i4]-(t1[i]+xd-t1[n-i2])});
                    }else{
                        dp[i][i2][i3][i4]=max({dp[i][i2][i3][i4],
                        min(dp[i][i2+1][i3][i4-1]-(t1[n-i2+1]-t1[n-i2]),t2[n-i2+1]),
                            dp[i][i2+1][i3][i4]-(t1[n-i2+1]-t1[n-i2]),
                        min(dp[i+1][i2][0][i4-1]-(xd-t1[n-i2+1]+t1[i+1]),t2[n-i2+1]),
                            dp[i+1][i2][0][i4]-(xd-t1[n-i2+1]+t1[i+1])});
                    }                    
                }
            }
        }
    }
    int res=0;
    for(int i=1;i<=n;i++){
        if(dp[1][0][0][i]-t1[1]>=0 or dp[0][1][1][i]-(xd-t1[n])>=0) res=i;
    }
    cout<<res<<"\n";
}
int main(){
    ios_base::sync_with_stdio(0),cin.tie(0);
    int tt=1;
    while(tt--) solve();
}

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