Submission #245054

#TimeUsernameProblemLanguageResultExecution timeMemory
245054vioalbertCollecting Stamps 3 (JOI20_ho_t3)C++14
25 / 100
2091 ms114948 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; const ll N = 205; ll n, l; ll cl[N], ccl[N], t[N]; void read() { cin >> n >> l; for(int i = 1; i <= n; i++) { cin >> cl[i]; ccl[i] = l - cl[i]; } for(int i = 1; i <= n; i++) cin >> t[i]; } struct state { int l, r, cnt, dir; state(int _l, int _r, int _cnt, int _dir) : l(_l), r(_r), cnt(_cnt), dir(_dir) {} bool operator<(const state& ot) const { return cnt < ot.cnt; } }; void solve() { priority_queue<pair<ll, state>, vector<pair<ll, state>>, greater<pair<ll, state>>> pq; ll dist[n+2][n+2][n+2][2]; for(int i = 1; i <= n+1; i++) { for(int j = i-1; j <= n; j++) { for(int k = 0; k <= n; k++) dist[i][j][k][0] = dist[i][j][k][1] = -1; } } ll cost, total; int ans = 0; pq.emplace(0, state(1, n, 0, 0)); dist[1][n][0][0] = 0; while(!pq.empty()) { ll d = pq.top().first; state u = pq.top().second; pq.pop(); if(dist[u.l][u.r][u.cnt][u.dir] == d) { if(u.l > u.r) { ans = max(ans, u.cnt); continue; } if(u.dir == 0) { cost = ((u.l==1)?0:-cl[u.l-1]) + cl[u.l]; total = d + cost; ll& nxt1 = dist[u.l+1][u.r][u.cnt + (total <= t[u.l])][0]; if(nxt1 == -1 || nxt1 > total) { nxt1 = total; pq.emplace(nxt1, state(u.l+1, u.r, u.cnt + (total <= t[u.l]), 0)); } cost = ((u.l==1)?0:cl[u.l-1]) + ccl[u.r]; total = d + cost; ll& nxt2 = dist[u.l][u.r-1][u.cnt + (total <= t[u.r])][1]; if(nxt2 == -1 || nxt2 > total) { nxt2 = total; pq.emplace(nxt2, state(u.l, u.r-1, u.cnt + (total <= t[u.r]), 1)); } } else { cost = ((u.r==n)?0:-ccl[u.r+1]) + ccl[u.r]; total = d + cost; ll& nxt1 = dist[u.l][u.r-1][u.cnt + (total <= t[u.r])][1]; if(nxt1 == -1 || nxt1 > total) { nxt1 = total; pq.emplace(nxt1, state(u.l, u.r-1, u.cnt + (total <= t[u.r]), 1)); } cost = ((u.r==n)?0:ccl[u.r+1]) + cl[u.l]; total = d + cost; ll& nxt2 = dist[u.l+1][u.r][u.cnt + (total <= t[u.l])][0]; if(nxt2 == -1 || nxt2 > total) { nxt2 = total; pq.emplace(nxt2, state(u.l+1, u.r, u.cnt + (total <= t[u.l]), 0)); } } } } cout << ans << '\n'; } int main() { ios::sync_with_stdio(0); cin.tie(0); read(); solve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...