Submission #245043

#TimeUsernameProblemLanguageResultExecution timeMemory
245043vioalbertCollecting Stamps 3 (JOI20_ho_t3)C++14
25 / 100
2081 ms115028 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; 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; } } 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:36: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...