Submission #1054130

#TimeUsernameProblemLanguageResultExecution timeMemory
1054130vako_pIce Hockey World Championship (CEOI15_bobek)C++14
100 / 100
902 ms78544 KiB
#include <bits/stdc++.h> using namespace std; #define ll long long #define pb push_back const int mxN = 50; ll n,m,a[mxN]; int _p[2000000]; int* p = _p + 5; map<ll,int> ans; vector<ll> v; int main(){ ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m; for(int i = 0; i < n; i++) cin >> a[i]; v.pb(0); ans[0]++; for(int bit = 1; bit < (1 << (n / 2)); bit++){ ll x = 0; for(int i = 0; i < (n / 2); i++) x += a[i] * (((1 << i) & bit) > 0); if(x <= m){ if(!ans[x]) v.pb(x); ans[x]++; } // cout << x << ' ' << ans[x] << '\n'; } sort(v.begin(), v.end()); for(int i = 0; i < v.size(); i++) p[i] = p[i - 1] + ans[v[i]]; ll res = p[v.size() - 1]; for(int bit = 1; bit < (1 << ((n + 1) / 2)); bit++){ ll x = 0; for(int i = 0; i < (n + 1) / 2; i++) x += a[i + n / 2] * (((1 << i) & bit) > 0); auto it = upper_bound(v.begin(), v.end(), m - x); if(it != v.begin()) res += p[it - v.begin() - 1]; } cout << res; }

Compilation message (stderr)

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