Submission #253276

#	Time	Username	Problem	Language	Result	Execution time	Memory
253276		doowey	Collecting Stamps 3 (JOI20_ho_t3)	C++14	100 / 100	1363 ms	152300 KiB

ho_t3

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

struct State{
    ll dist;
    int to_left;
    int to_right;
    int collect;
    int side;
    bool operator< (const State &Q) const {
        return dist > Q.dist;
    }
};

const int N = 201;
const ll inf = (ll)1e18;
ll dp[N][N][N][2];
ll x[N], t[N];

priority_queue<State> bf;

void upd_state(State nx){
    if(nx.dist < dp[nx.to_left][nx.to_right][nx.collect][nx.side]){
        dp[nx.to_left][nx.to_right][nx.collect][nx.side] = nx.dist;
        bf.push(nx);
    }
}

int main(){
    fastIO;
    int n;
    ll d;
    cin >> n >> d;
    for(int i = 1 ; i <= n; i ++ ){
        cin >> x[i];
    }
    for(int i = 1; i <= n; i ++ ){
        cin >> t[i];
    }
    for(int i = 0 ; i <= n; i ++ ){
        for(int j = 0 ; j <= n; j ++ ){
            for(int k = 0; k <= n; k ++ ){
                for(int b = 0; b < 2; b ++ ){
                    dp[i][j][k][b] = inf;
                }
            }
        }
    }
    int m = (n + 1);
    x[m]=d,t[m]=0;
    x[0]=0,t[0]=0;
    int ans = 0;
    upd_state({0, 0, 0, 0, 0});
    State cur;
    State nx;
    ll dnw;
    while(!bf.empty()){
        cur = bf.top();
        bf.pop();
        ans = max(ans, cur.collect);
        if(cur.dist != dp[cur.to_left][cur.to_right][cur.collect][cur.side])
            continue;
        upd_state({cur.dist + x[cur.to_right] + d-x[m - cur.to_left], cur.to_left, cur.to_right, cur.collect, cur.side ^ 1});
        if(cur.to_left + cur.to_right < n){
            if(cur.side == 1){
                nx = {cur.dist, cur.to_left, cur.to_right + 1, cur.collect, 1};
                dnw = x[cur.to_right+1] - x[cur.to_right] + cur.dist;
                nx.dist = dnw;
                if(dnw <= t[cur.to_right + 1])
                    nx.collect ++ ;
                upd_state(nx);
            }
            if(cur.side == 0){
                nx = {cur.dist, cur.to_left + 1, cur.to_right, cur.collect, 0};
                dnw = x[m - cur.to_left]-x[m - cur.to_left - 1] + cur.dist;
                nx.dist = dnw;
                if(dnw <= t[m - cur.to_left - 1])
                    nx.collect ++ ;
                upd_state(nx);
            }
        }
    }
    cout << ans << "\n";
    return 0;
}

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