제출 #588672

#제출 시각아이디문제언어결과실행 시간메모리
588672peuchUplifting Excursion (BOI22_vault)C++17
5 / 100
5049 ms20712 KiB
#include<bits/stdc++.h> using namespace std; #pragma GCC optimize("Ofast") #pragma GCC target("avx,avx2,fma") const int MAXN = 101; const int MAXA = 101 * 100 * 101; const long long INF = 1e18; const int HALF = MAXA / 2; int m; long long l; long long v[2 * MAXN]; long long dp[2][MAXA]; int found[MAXA], marc[MAXA]; int fim = 0; int main(){ scanf("%d %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] = dp[0][j] = INF; dp[0][HALF] = 0; marc[HALF] = 1; found[0] = HALF; for(auto val : moedas){ queue<int> auxFound; for(int k = 0; k <= fim; k++){ int j = found[k]; if(j + val.first >= MAXA && j + val.first < 0) continue; dp[1][j + val.first] = min(dp[1][j + val.first], dp[0][j] + val.second); auxFound.push(j + val.first); } while(!auxFound.empty()){ int j = auxFound.front(); auxFound.pop(); dp[0][j] = min(dp[0][j], dp[1][j]); if(!marc[j]) marc[j] = 1, found[++fim] = j; } } if(dp[0][sum - l + HALF] == INF) printf("impossible\n"); else printf("%lld\n", cnt - dp[0][sum - l + HALF]); }

컴파일 시 표준 에러 (stderr) 메시지

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