Submission #967724

#TimeUsernameProblemLanguageResultExecution timeMemory
967724vjudge1Ice Hockey World Championship (CEOI15_bobek)C++17
100 / 100
299 ms34452 KiB
#include <bits/stdc++.h> #define ll long long using namespace std; ll n, m, arr[50], res1[1100010], res2[1100010], ans; vector<ll> dp1, dp2; void find(int idx, ll mon, int cur, int lim, ll res[]) { if(cur > lim) { res[idx] = mon; return; } if(mon + arr[cur] <= m) find(idx+pow(2, lim-cur), mon+arr[cur], cur+1, lim, res); find(idx, mon, cur+1, lim, res); if(cur == lim) res[idx] = mon; } int main() { cin.tie(0)->sync_with_stdio(0); cin >> n >> m; for(int i=1; i<=n; i++) { cin >> arr[i]; } for(int i=0; i<1100010; i++) { res1[i] = -1; res2[i] = -1; } find(0, 0, 1, n/2, res1); find(0, 0, (n/2)+1, n, res2); for(int i=0; i<1100010; i++) { if(res1[i] != -1) dp1.push_back(res1[i]); if(res2[i] != -1) dp2.push_back(res2[i]); } sort(dp2.begin(), dp2.end()); for(int i=0; i<dp1.size(); i++) { ans += lower_bound(dp2.begin(), dp2.end(), m-dp1[i]+1) - dp2.begin(); } cout << ans; }

Compilation message (stderr)

bobek.cpp: In function 'int main()':
bobek.cpp:35:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     for(int i=0; i<dp1.size(); i++) {
      |                  ~^~~~~~~~~~~
#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...