Submission #1046139

#TimeUsernameProblemLanguageResultExecution timeMemory
1046139ByeWorldIce Hockey World Championship (CEOI15_bobek)C++14
100 / 100
233 ms33304 KiB
#include <bits/stdc++.h> #pragma GCC optimize("O3") #define int long long #define ll long long #define pb push_back #define fi first #define se second #define lf (id<<1) #define rg ((id<<1)|1) #define md ((l+r)>>1) #define ld long double using namespace std; typedef pair<int,int> pii; typedef pair<int,pii> ipii; typedef pair<ld,ld> pll; const int MAXN = 3e5+15; const int INF = 3e18+10; const int MX = 2e18; void chmn(int &a, int b){ a = min(a, b); } void chmx(int &a, int b){ a = max(a, b); } mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); int n, m; int a[45]; signed main(){ // ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> n >> m; for(int i=1; i<=n; i++) cin >> a[i]; vector <int> fr, sc; fr.pb(0); sc.pb(0); for(int i=1; i<=n/2; i++){ vector <int> vec; for(auto in : fr){ vec.pb(in); if(in+a[i] <= m) vec.pb(in+a[i]); } swap(vec, fr); } for(int i=n/2+1; i<=n; i++){ vector <int> vec; for(auto in : sc){ vec.pb(in); if(in+a[i] <= m) vec.pb(in+a[i]); } swap(vec, sc); } sort(sc.begin(), sc.end()); // for(auto in : sc) cout << in << ' '; // cout << "sc\n"; int ans = 0; for(auto in : fr){ // cout << in << " in\n"; // cout << upper_bound(sc.begin(), sc.end(), m-in)-sc.begin()-1 << '\n'; int te = (int)(upper_bound(sc.begin(), sc.end(), m-in)-sc.begin()); ans += te; } cout << ans << '\n'; }
#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...