Submission #844678

#	Time	Username	Problem	Language	Result	Execution time	Memory
844678		anton	Collecting Stamps 3 (JOI20_ho_t3)	C++17	25 / 100	992 ms	98732 KiB

ho_t3

#include<bits/stdc++.h>

using namespace std;
#define int long long

const int MAX_N = 201;
const int INF = 1e17;
int N, L;
int dp[MAX_N][MAX_N][MAX_N];
int X[MAX_N];
int T[MAX_N];


struct Node{
    int t;

    int cur, other;
    int has;

    Node(int _t, int _cur, int _other, int _has){
        t = _t;
        cur = _cur;
        other = _other;
        has = _has;
    }

    bool operator<(const Node &b)const{
        return t>b.t;
    }
};

vector<Node> gen_neig(Node& cur){
    int left, right;
    left = max(cur.cur, cur.other);
    right = min(cur.cur, cur.other);

    //cout<<left<<" "<<right<<" "<<cur.t<<" "<<cur.has<<endl;

    vector<Node> res;
    if(cur.cur == left){
        if(left>right){
            int new_time = cur.t + ((X[(left+1)%L] - X[left] +L)%L);
            if(new_time<=T[left]){
                res.push_back(Node(new_time, left-1, right, cur.has +1));
            }
            else{
                res.push_back(Node(new_time, left-1, right, cur.has));
            }
            
        }
    }
    if(cur.cur == right){
        if(left>right){
            int new_time = cur.t + abs(X[right]- X[right+1]);
            if(new_time<=T[right+1]){
                res.push_back(Node(new_time, right+1, left, cur.has +1));
            }
            else{
                res.push_back(Node(new_time, right+1, left, cur.has));
            }
        }
    }
    ////cout<<"pos L: "<<X[(left+1)%L]<<endl;
    res.push_back(Node(cur.t + abs( (L - X[(left+1)%L])%L+ X[right]), cur.other, cur.cur, cur.has));
    return res;
}

signed main(){
    cin>>N>>L;
    N++;
    X[0]  =0;

    fill(dp[0][0], dp[MAX_N-1][MAX_N-1], INF);

    T[0]=  INF;
    for(int i = 1; i<N; i++){
        cin>>X[i];
    }

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


    priority_queue<Node> pq;

    pq.push(Node(0, 0, N-1, 0));
    dp[0][N-1][0] = 0;

    while(pq.size()>0){
        auto cur = pq.top();
        pq.pop();

        ////cout<<cur.cur<<" "<<cur.other<<" "<<cur.has<<" "<<cur.t<<endl;


        if(dp[cur.cur][cur.other][cur.has] == cur.t){
            //cout<<"actual"<<endl;
            auto neigs = gen_neig(cur);
            for(auto v: neigs){
                if(dp[v.cur][v.other][v.has]> v.t){
                    pq.push(v);
                    dp[v.cur][v.other][v.has] = v.t;
                }
            }
        }
        else{
            //cout<<dp[cur.cur][cur.other][cur.has]<<endl;
        }
    }

    int best = 0;
    for(int i = 0; i<N; i++){
        for(int j = 0; j<=N; j++){
            if(dp[i][i][j] <INF){
                best = max(best, j);
            }
        }
    }

    cout<<best<<endl;
}

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