제출 #1074802

#제출 시각아이디문제언어결과실행 시간메모리
1074802socpiteUplifting Excursion (BOI22_vault)C++17
80 / 100
5065 ms10228 KiB
#include<bits/stdc++.h> using namespace std; const long long INF = 1e18; const int maxn = 305; long long A[2*maxn], inp[2*maxn]; int bs_A[2*maxn][65]; vector<pair<int, long long>> g[65][maxn]; long long dp[2][4*maxn*maxn]; long long tmp[4*maxn*maxn]; long long mx(const long long &a, const long long &b){return a > b ? a : b;} int main(){ ios::sync_with_stdio(false); cin.tie(0); int m; long long L; cin >> m >> L; for(int i = 0; i <= 2*m; i++)cin >> A[i]; if(L < 0){ L*=-1; for(int i = 1; i <= m; i++)swap(A[m-i], A[m+i]); } for(int i = 0; i <= 2*m; i++){ if(i == m)continue; for(int j = 0; j <= 60; j++){ if(A[i] == 0)break; bs_A[i][j] = A[i]&1 ? 1 : 2; A[i] = (A[i]-1)/2; } } for(int b = 0; b <= 60; b++){ for(int i = 1; i <= m; i++){ map<int, long long> mp; for(int p_val = 0; p_val <= bs_A[m+i][b]; p_val++){ for(int n_val = 0; n_val <= bs_A[m-i][b]; n_val++){ mp[(p_val - n_val)*i] = max<long long>(mp[(p_val - n_val)*i], p_val + n_val); } } for(auto v: mp)g[b][i].push_back({v.first, v.second<<b}); } } int sum = m*(m+1)*2; for(int i = 0; i <= 2*sum; i++)dp[0][i] = dp[1][i] = -INF; dp[0][sum] = 0; for(int b = 0; b <= 60; b++){ for(int i = 1; i <= m; i++){ for(auto v: g[b][i])for(int j = (v.first > 0 ? 0 : -v.first); j <= (v.first > 0 ? 2*sum - v.first : 2*sum); j++)dp[i&1][j + v.first] = mx(dp[i&1][j + v.first], dp[(i&1)^1][j] + v.second); } for(int j = 0; j <= 2*sum; j++)tmp[j] = -INF; for(int i = 0; i <= 2*sum; i++){ if(((i&1)^(sum&1)) != ((L>>b)&1))continue; int ri = i - sum, pos; if(ri < 0)pos = (ri-1)/2 + sum; else pos = ri/2 + sum; assert(pos >= 0 && pos <= 2*sum); tmp[pos] = max(tmp[pos], dp[m&1][i]); } for(int i = 0; i <= 2*sum; i++){ dp[0][i] = tmp[i]; dp[1][i] = -INF; } } if(dp[0][sum] < 0)cout << "impossible"; else cout << dp[0][sum] + A[m]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...