제출 #1163019

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1163019		tw20000807	Collecting Stamps 3 (JOI20_ho_t3)	C++20	100 / 100	1622 ms	168688 KiB

ho_t3

#include<bits/stdc++.h>
#define int long long
#define all(v) v.begin(), v.end()
#define SZ(x) (int)x.size()
#define pii pair<int, int>
#define X first
#define Y second

using namespace std;
const int maxn = 2e5 + 10;
const int mod = 1e9 + 7;//    998244353;
const int llmx = 1e18;

int dis[2][201][201][201];

void sol(){
    int n, L;
    cin >> n >> L;
    vector< int > x(n + 1);
    vector< int > t(n + 1, -1);
    for(int i = 1; i <= n; ++i) cin >> x[i];
    for(int i = 1; i <= n; ++i) cin >> t[i];
    int ans = 0;
    priority_queue< array<int, 5>, vector< array<int, 5> >, greater< array<int, 5> > > pq;
    for(int f : {0, 1}) for(int i = 0; i <= n; ++i) for(int j = 0; j <= n; ++j) for(int k = 0; k <= n; ++k) dis[f][i][j][k] = llmx;
    dis[0][0][0][0] = 0, dis[1][0][0][0] = 0;
    pq.push({0, 0, 0, 0, 0});
    pq.push({0, 1, 0, 0, 0});
    auto F = [&](int l, int r) -> int {
        return min(abs(x[r] - x[l]), L - abs(x[r] - x[l]));
    };
    while(!pq.empty()){
        auto [D, f, l, r, ct] = pq.top(); pq.pop();
        // cerr << D << " " << f << " " << l << " " << r << " " << ct << "!!\n";
        // L : 0, R : 1
        int nl = (l + n) % (n + 1);
        int nr = (r + 1) % (n + 1);
        ans = max(ans, ct);
        if(nl != r){
            int tim = D + F(f ? r : l, nl);
            int nct = ct + (tim <= t[nl]);
            if(dis[0][nl][r][nct] > tim){
                dis[0][nl][r][nct] = tim;
                pq.push({dis[0][nl][r][nct], 0, nl, r, nct});
            }
        }
        if(nr != l){
            int tim = D + F(f ? r : l, nr);
            int nct = ct + (tim <= t[nr]);
            if(dis[1][l][nr][nct] > tim){
                dis[1][l][nr][nct] = tim;
                pq.push({dis[1][l][nr][nct], 1, l, nr, nct});
            }
        }
    }
    cout << ans << "\n";
}
/*
6 25
3 4 7 17 21 23
11 7 17 10 8 10
// 4


5 20
4 5 8 13 17
18 23 15 7 10
// 5

4 19
3 7 12 14
2 0 5 4
// 0

10 87
9 23 33 38 42 44 45 62 67 78
15 91 7 27 31 53 12 91 89 46
// 5

*/
signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cerr.tie(0);
    int t = 1; //cin >> t;
    while(t--) sol();
}

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