Submission #245038

#TimeUsernameProblemLanguageResultExecution timeMemory
245038vioalbertCollecting Stamps 3 (JOI20_ho_t3)C++14
25 / 100
2095 ms179044 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; cl[0] = ccl[0] = 0; 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; bool 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]; memset(dist, -1, sizeof dist); int ans = 0; pq.push({0, {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; } ll cost, total; 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.push({nxt1, {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.push({nxt2, {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.push({nxt1, {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.push({nxt2, {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; }

Compilation message (stderr)

ho_t3.cpp: In function 'void solve()':
ho_t3.cpp:32:27: warning: narrowing conversion of 'n' from 'll {aka long long int}' to 'int' inside { } [-Wnarrowing]
  pq.push({0, {1, n, 0, 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...