Submission #588655

#TimeUsernameProblemLanguageResultExecution timeMemory
588655peuchUplifting Excursion (BOI22_vault)C++17
0 / 100
5050 ms145336 KiB
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") const long long MAXN = 210; const long long MAXA = MAXN * MAXN * MAXN; const long long INF = 1e18; const long long HALF = MAXA / 2; long long m; long long l; long long v[2 * MAXN]; long long dp[2][MAXA]; int main(){ scanf("%lld %lld", &m, &l); long long sum = 0; long long cnt = 0; vector<pair<long long, long long> > moedas; for(long long i = -m; i <= m; i++){ scanf("%lld", &v[i + m]); sum += v[i + m] * i; cnt += v[i + m]; long long aux = v[i + m]; long long tam = 1; while(aux > 0){ moedas.push_back(make_pair(i * tam, tam)); aux--; if(aux % 2 == 1){ moedas.push_back(make_pair(i * tam, tam)); aux--; } aux /= 2; tam *= 2; } } if(l + HALF >= MAXA || l + HALF < 0){ printf("impossible\n"); return 0; } for(long long j = 0; j < MAXA; j++) dp[1][j] = INF; dp[1][HALF] = 0; for(auto val : moedas){ swap(dp[0], dp[1]); for(long long j = 0; j < MAXA; j++){ dp[1][j] = dp[0][j]; if(j - val.first < MAXA && j - val.first >= 0) dp[1][j] = min(dp[1][j], dp[0][j - val.first] + val.second); } } if(dp[1][sum - l + HALF] == INF) printf("impossible\n"); else printf("%lld\n", cnt - dp[1][sum - l + HALF]); }

Compilation message (stderr)

vault.cpp: In function 'int main()':
vault.cpp:20:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   20 |  scanf("%lld %lld", &m, &l);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~
vault.cpp:25:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |   scanf("%lld", &v[i + 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...