Submission #244958

#TimeUsernameProblemLanguageResultExecution timeMemory
244958vioalbertCollecting Stamps 3 (JOI20_ho_t3)C++14
15 / 100
2013 ms168128 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], idx[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]; idx[i] = 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]; bool vis[n+2][n+2][n+2][2]; for(int i = 0; i <= n+1; i++) { for(int j = 0; j <= n+1; j++) { for(int k = 0; k <= n+1; k++) { dist[i][j][k][0] = dist[i][j][k][1] = 1e15; vis[i][j][k][0] = vis[i][j][k][1] = 0; } } } int ans = 0; pq.push({0, {1, n, 0, 0}}); dist[1][n][0][0] = 0; while(!pq.empty()) { state u = pq.top().second; pq.pop(); if(!vis[u.l][u.r][u.cnt][u.dir]) { vis[u.l][u.r][u.cnt][u.dir] = 1; // cerr << u.l << ' ' << u.r << ' ' << u.cnt << ' ' << u.dir << '\n'; // cerr << dist[u.l][u.r][u.cnt][u.dir] << '\n'; 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 = dist[u.l][u.r][u.cnt][u.dir] + cost; if(dist[u.l+1][u.r][u.cnt + (total <= t[u.l])][0] > total) { dist[u.l+1][u.r][u.cnt + (total <= t[u.l])][0] = total; pq.push({dist[u.l+1][u.r][u.cnt + (total <= t[u.l])][0], {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 = dist[u.l][u.r][u.cnt][u.dir] + cost; if(dist[u.l][u.r-1][u.cnt + (total <= t[u.r])][1] > total) { dist[u.l][u.r-1][u.cnt + (total <= t[u.r])][1] = total; pq.push({dist[u.l][u.r-1][u.cnt + (total <= t[u.r])][1], {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 = dist[u.l][u.r][u.cnt][u.dir] + cost; if(dist[u.l][u.r-1][u.cnt + (total <= t[u.r])][1] > total) { dist[u.l][u.r-1][u.cnt + (total <= t[u.r])][1] = total; pq.push({dist[u.l][u.r-1][u.cnt + (total <= t[u.r])][1], {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 = dist[u.l][u.r][u.cnt][u.dir] + cost; if(dist[u.l+1][u.r][u.cnt + (total <= t[u.l])][0] > total) { dist[u.l+1][u.r][u.cnt + (total <= t[u.l])][0] = total; pq.push({dist[u.l+1][u.r][u.cnt + (total <= t[u.l])][0], {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:41: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...