Submission #1091683

#	Time	Username	Problem	Language	Result	Execution time	Memory
1091683		akim9905	Collecting Stamps 3 (JOI20_ho_t3)	C++17	100 / 100	759 ms	516756 KiB

ho_t3

#include <bits/stdc++.h>
using namespace std;

#define fileio() freopen("input.txt","r",stdin); freopen("output.txt","w",stdout)
#define fio() ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) (x).begin(), (x).end()
#define allr(x) x.rbegin(), x.rend()
#define cmprs(x) sort(all(x)),x.erase(unique(all(x)),x.end())
#define endl "\n"
#define sp " "
#define pb push_back
#define lb lower_bound
#define ub upper_bound
#define F first
#define S second
#define rz resize
#define sz(a) (int)(a.size())
#define clr(a) a.clear()

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef tuple<int, int, int> tpi;
typedef tuple<ll, ll, ll> tpl;
typedef pair<double, ll> pdl;
typedef pair<double, int> pdi;

const int dx[] = {1,-1,0,0,1,1,-1,-1};
const int dy[] = {0,0,1,-1,1,-1,1,-1};
const ll MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3f;
const int MAX = 404; // PLZ CHK!

int N,L,X[MAX],T[MAX];
int D[MAX][MAX][2][MAX];

int go(int l, int r, int p, int s) {
    if (l==N+1 && r==N+1 && s==0) return 0;
    if (l>=r) return INF;

    int &ret=D[l][r][p][s];
    if (ret!=-1) return ret;

    ret=INF;
    if (p) {
        ret=min(ret, go(l,r-1,1,s)+abs(X[r]-X[r-1]));
        ret=min(ret, go(l,r-1,0,s)+abs(X[r]-X[l]));
        if (s-1>=0) {
            int t1=go(l,r-1,1,s-1)+abs(X[r]-X[r-1]);
            int t2=go(l,r-1,0,s-1)+abs(X[r]-X[l]);
            if (t1<=T[r]) ret=min(ret, t1);
            if (t2<=T[r]) ret=min(ret, t2);
        }
    }
    else {
        ret=min(ret, go(l+1,r,0,s)+abs(X[l]-X[l+1]));
        ret=min(ret, go(l+1,r,1,s)+abs(X[l]-X[r]));
        if (s-1>=0) {
            int t1=go(l+1,r,0,s-1)+abs(X[l]-X[l+1]);
            int t2=go(l+1,r,1,s-1)+abs(X[l]-X[r]);
            if (t1<=T[l]) ret=min(ret, t1);
            if (t2<=T[l]) ret=min(ret, t2);
        }
    }

    return ret;
}

int main() {
    fio();
    memset(D,-1,sizeof D);

    cin>>N>>L;
    for (int i=1; i<=N; i++) cin>>X[i];
    for (int i=1; i<=N; i++) cin>>T[i];    

    X[N+1]=L;
    for (int i=N+2; i<=2*N+1; i++) X[i]=X[i-N-1]+L, T[i]=T[i-N-1];

    int ans=0;
    for (int l=1,r=N+1; l<=N+1; l++,r++) {
        for (int s=0; s<=N; s++) {
            if (go(l,r,0,s)<INF) ans=max(ans,s);
            if (go(l,r,1,s)<INF) ans=max(ans,s);
        }
    }
    
    cout<<ans;
    return 0;
}

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