Submission #145680

#TimeUsernameProblemLanguageResultExecution timeMemory
145680heonSan (COCI17_san)C++17
120 / 120
472 ms21060 KiB
#include <iostream> #include <cstdio> #include <cstdlib> #include <algorithm> #include <cmath> #include <vector> #include <set> #include <map> #include <unordered_set> #include <unordered_map> #include <queue> #include <ctime> #include <cassert> #include <complex> #include <string> #include <cstring> #include <chrono> #include <random> #include <queue> #include <bitset> #include <stack> #include <iomanip> using namespace std; #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() typedef vector <int> vi; typedef pair<int,int> ii; typedef long long ll; typedef long double ld; const int mod = 1e9 + 7; const ll inf = 3e18 + 5; int add(int a, int b) { return (a += b) < mod ? a : a - mod; } int mul(int a, int b) { return 1LL * a * b % mod; } int h[41], g[41]; int n; vector<pair<int, ll>> v; vector<pair<ll, int>> u; void f(int i, ll coins){ for(int j = i + 1; j < n / 2; j++){ if(h[i] <= h[j]){ f(j, coins + g[j]); } } v.emplace_back(h[i], coins); } void ff(int i, ll coins, int start){ for(int j = i + 1; j < n; j++){ if(h[i] <= h[j]){ ff(j, coins + g[j], start); } } u.emplace_back(coins, start); } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); ll k; cin >> n >> k; for(int i = 0; i < n; i++) cin >> h[i] >> g[i]; for(int i = 0; i < n / 2; i++) f(i, g[i]); for(int i = n / 2; i < n; i++) ff(i, g[i], i); h[n] = 1e9 + 5; v.emplace_back(0, 0); u.emplace_back(0, n); sort(all(v)); sort(all(u)); ll res = 0; unordered_map<int, vector <ll>> ump; for(auto [coins, start] : u){ ump[start].push_back(coins); } for(auto [endh, coins] : v){ for(int i = n / 2; i <= n; i++){ if(h[i] >= endh){ res += ump[i].end() - lower_bound(all(ump[i]), k - coins); } } } cout << res; }
#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...