oj.uz

Submission #747768

# Submission time Handle Problem Language Result Execution time Memory
747768 2023-05-24T16:27:23 Z prairie2022 Collecting Stamps 3 (JOI20_ho_t3) C++14
0 / 100
 1 ms 340 KB 
#include <bits/stdc++.h>
typedef long long ll;
#define fastio cin.tie(0), cout.tie(0), ios::sync_with_stdio(0);
#define F first 
#define S second
#define vst vis[tmp.w[0]][tmp.w[1]][tmp.b]
using namespace std;

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

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;
    fastio
    //informations
    cin >> n >> L;
    x[0][0] = x[0][1] = 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Incorrect 0 ms 212 KB Output isn't correct
4 Halted 0 ms 0 KB -