Submission #747785

#	Time	Username	Problem	Language	Result	Execution time	Memory
747785		prairie2022	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	169 ms	5868 KiB

ho_t3

#include <bits/stdc++.h>
typedef long long ll;
#define fastio cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
#define vst vis[tmp.b][tmp.w[0]][tmp.w[1]]
using namespace std;

const int M = 1e9;
int n, L, ans=0;
int x[2][201], d[2][201];
int vis[2][201][201];

struct dp{
    int t, c, w[2];
    bool b;
    inline bool forward(){
        if(w[0]+w[1]==n) return 0;
        w[b]++;
        t += x[b][w[b]]-x[b][w[b]-1];
        if(t>M) return 0;
        if(t<=d[b][w[b]]) c++;
        return 1;
    }
    inline bool backward(){
        if(w[0]+w[1]==n) return 0;
        b = !b;
        w[b]++;
        t += x[b][w[b]]+x[!b][w[!b]];
        if(t>M) return 0;
        if(t<=d[b][w[b]]) c++;
        return 1;
    }
};

inline bool cmp(dp dp1, dp dp2){
    return dp1.t > dp2.t;
}

priority_queue<dp, vector<dp>, decltype(&cmp)> pq(cmp);

int main(){
    dp tmp, ins;
    for(int i=0; i<201; i++){
        fill(vis[0][i], vis[0][i]+201, -1);
        fill(vis[1][i], vis[1][i]+201, -1);
    }
    fastio
    //informations
    cin >> n >> L;
    x[0][0] = x[1][0] = 0;
    for(int i=1; i<=n; i++){
        cin >> x[0][i];
        x[1][n+1-i] = L-x[0][i];
    }
    for(int i=1; i<=n; i++){
        cin >> d[0][i];
        d[1][n+1-i] = d[0][i];
    }
    //dp
    pq.push({0, 0, {0, 0}, 0});
    while(!pq.empty() && pq.top().t<=M){
        tmp = pq.top();
        pq.pop();
        //cout << tmp.t << ' ' << tmp.c << ' ' << tmp.w[0] << ' ' << tmp.w[1] << ' ' << (int)tmp.b << '\n';
        if(tmp.c<=vst) continue;
        vst = tmp.c;
        ans = max(ans, tmp.c);
        ins = tmp;
        if(ins.forward()) pq.push(ins);
        ins = tmp;
        if(ins.backward()) pq.push(ins);
    }
    cout << ans << '\n';
    return 0;
}

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