Submission #803452

#TimeUsernameProblemLanguageResultExecution timeMemory
803452raysh07Ice Hockey World Championship (CEOI15_bobek)C++17
100 / 100
55 ms33196 KiB
#include <bits/stdc++.h> using namespace std; //#define int long long #define INF (int)1e18 #define f first #define s second mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count()); vector <long long> gen(vector <long long> a){ if (a.size() == 0){ vector <long long> res; res.push_back(0); return res; } long long x = a.back(); a.pop_back(); vector <long long> v = gen(a); vector <long long> res; int p1 = 0; for (auto y : v){ while (p1 != v.size() && v[p1] + x < y){ res.push_back(v[p1] + x); p1++; } res.push_back(y); } while (p1 != v.size()){ res.push_back(v[p1] + x); p1++; } return res; } void Solve() { int n; long long m; cin >> n >> m; vector <long long> a, b; for (int i = 0; i < n; i++){ long long x; cin >> x; if (i < 20){ a.push_back(x); } else { b.push_back(x); } } vector <long long> v1 = gen(a); vector <long long> v2 = gen(b); // sort(v1.begin(), v1.end()); // sort(v2.begin(), v2.end()); int ptr = 0; long long ans = 0; reverse(v1.begin(), v1.end()); for (auto x : v1){ while (ptr != v2.size() && x + v2[ptr] <= m){ ptr++; } ans += ptr; } cout << ans << "\n"; } int32_t main() { auto begin = std::chrono::high_resolution_clock::now(); ios_base::sync_with_stdio(0); cin.tie(0); int t = 1; // cin >> t; for(int i = 1; i <= t; i++) { //cout << "Case #" << i << ": "; Solve(); } auto end = std::chrono::high_resolution_clock::now(); auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin); cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; return 0; }

Compilation message (stderr)

bobek.cpp: In function 'std::vector<long long int> gen(std::vector<long long int>)':
bobek.cpp:25:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         while (p1 != v.size() && v[p1] + x < y){
      |                ~~~^~~~~~~~~~~
bobek.cpp:33:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |     while (p1 != v.size()){
      |            ~~~^~~~~~~~~~~
bobek.cpp: In function 'void Solve()':
bobek.cpp:65:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         while (ptr != v2.size() && x + v2[ptr] <= 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...