Submission #588661

#TimeUsernameProblemLanguageResultExecution timeMemory
588661peuchUplifting Excursion (BOI22_vault)C++17
0 / 100
3910 ms524288 KiB
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") const long long MAXN = 101; const long long MAXA = 101 * 100 * 101; 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; multiset<pair<long long, long long> > auxMoedas; for(long long i = -m; i <= m; i++){ scanf("%lld", &v[i + m]); sum += v[i + m] * i; cnt += v[i + m]; for(int j = 0; j < v[i + m]; j++) auxMoedas.insert(make_pair(i, -1)); } vector<pair<long long, long long> > moedas; while(!auxMoedas.empty()){ pair<int, int> aux = *auxMoedas.begin(); auxMoedas.erase(auxMoedas.begin()); if(!moedas.empty() && moedas.back().first == aux.first){ if(!auxMoedas.empty() && auxMoedas.begin()->first == aux.first){ aux.first *= 2; aux.second += auxMoedas.begin()->second; auxMoedas.erase(auxMoedas.begin()); auxMoedas.insert(aux); continue; } } moedas.push_back(aux); } 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){ // printf("%lld %lld\n", val.first, val.second); 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...