Submission #1146703

#	Time	Username	Problem	Language	Result	Execution time	Memory
1146703		koukirocks	Collecting Stamps 3 (JOI20_ho_t3)	C++20	100 / 100	27 ms	2444 KiB

ho_t3

#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin()+1,(x).end()
#define F first
#define S second

using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
typedef pair<ll,ll> pll;
const int INF=0x3f3f3f3f;
const ll oo=0x3f3f3f3f3f3f3f3f;
template<class T>
using vvector = vector<vector<T>>;

pll dp[205][205][2];

int main() {
    speed;
    ll n,l;
    cin>>n>>l;
    vector<ll> t(n+1);
    vector<ll> x(n+1);
    for (int i=1;i<=n;i++) {
        cin>>x[i];
    }
    vector<ll> ptm(n+1);
    for (int i=1;i<=n;i++) {
        cin>>t[i];
        ptm[i]=t[i]-x[i];
    }
    sort(all(ptm));
    // for (int i=1;i<=n;i++) {
    //     cout<<ptm[i]<<" ";
    // }
    // cout<<" ptm\n";
    vvector<ll> prch(n+2,vector<ll>(n+1));
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=n;j++) {
            prch[i][j]=prch[i][j-1]+(t[j]-x[j]>=ptm[i]);
            // cout<<prch[i][j]<<" ";
        }
        // cout<<"\n";
    }
    // cout<<" prch\n";
    vector<ll> ntm(n+1);
    for (int i=1;i<=n;i++) {
        ntm[i]=t[i]-l+x[i];
    }
    sort(all(ntm));
    // for (int i=1;i<=n;i++) {
    //     cout<<ntm[i]<<" ";
    // }
    // cout<<" ntm\n";
    vvector<ll> nrch(n+2,vector<ll>(n+2));
    for (int i=1;i<=n;i++) {
        for (int j=n;j>=1;j--) {
            nrch[i][j]=nrch[i][j+1]+(t[j]-l+x[j]>=ntm[i]);
            // cout<<nrch[i][j]<<" ";
        }
        // cout<<"\n";
    }
    // cout<<"nrch\n";
    for (int i=1;i<=n;i++) {
        auto ti=lower_bound(all(ptm),0)-ptm.begin();
        dp[n+1][i][1]={prch[ti][i],x[i]};
        ti=lower_bound(all(ntm),0)-ntm.begin();
        dp[i][0][0]={nrch[ti][i],l-x[i]};
    }
    auto comp = [&](pll a,pll b) {
        pll c=max(pll(a.F,-a.S),{b.F,-b.S});
        return pll(c.F,-c.S);
    };
    for (int i=n;i>=1;i--) {
        for (int j=1;j<=n;j++) {
            dp[i][j][0]={0,oo};
            dp[i][j][1]={0,oo};
            if (n-i+1+j>n) continue;
            for (int k=i+1;k<=n+1;k++) {
                ll nt=dp[k][j][1].S+x[j];
                auto ti=lower_bound(all(ntm),nt)-ntm.begin();
                // cout<<k<<" "<<j<<" "<<ti<<" "<<nrch[ti][i]-nrch[ti][k]<<" "<<dp[k][j][1].F<<" "<<dp[k][j][1].S<<" kj ti rch dp 0\n";
                dp[i][j][0]=comp(dp[i][j][0],{dp[k][j][1].F+nrch[ti][i]-nrch[ti][k],nt+l-x[i]});
            }
            for (int k=0;k<j;k++) {
                ll nt=dp[i][k][0].S+l-x[i];
                auto ti=lower_bound(all(ptm),nt)-ptm.begin();
                // cout<<i<<" "<<k<<" "<<ti<<" ik ti 1\n";
                dp[i][j][1]=comp(dp[i][j][1],{dp[i][k][0].F+prch[ti][j]-prch[ti][k],nt+x[j]});
            }
            // cout<<i<<" "<<j<<" :\n";
            // cout<<dp[i][j][0].F<<" "<<dp[i][j][0].S<<"\n";
            // cout<<dp[i][j][1].F<<" "<<dp[i][j][1].S<<"\n";
        }
    }
    ll ans=0;
    for (int i=0;i<=n;i++) {
        ans=max(ans,dp[i+1][i][0].F);
        ans=max(ans,dp[i+1][i][1].F);
    }
    cout<<ans<<"\n";
    return 0;
}

/*
6 25
3 4 7 17 21 23
11 7 17 10 8 10
*/

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