Submission #197666

#TimeUsernameProblemLanguageResultExecution timeMemory
197666NeklixxSan (COCI17_san)C++14
96 / 120
1045 ms62668 KiB
#pragma GCC optimize("Ofast") #pragma comment(linker,"/stack:200000000") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #include <bits/stdc++.h> #define pb push_back #define mp make_pair #define F first #define S second #define all(v) v.begin(), v.end() #define sh cin.tie(0); cin.sync_with_stdio(0); cout.tie(0); #define FILE freopen("test.in", "r", stdin); #define vprint(v) for (int ii = 0; ii < v.size(); ii++){cout << v[ii] << " ";} #define debugv(v) if (v.size() != 0) {cout << "[ "; for (int __ = 0; __ < (int)(v.size()) - 1; __++){cout << v[__] << ", ";} cout << v[(int)(v.size()) - 1] << " ]" << endl;} else {cout << "[]" << endl;} #define debug cout << "-----------------------------------------------" << endl; #define print1(a) cout << "{ " << a << " }" << endl; #define print2(a, b) cout << "{ " << a << ", " << b << " }" << endl; #define print3(a, b, c) cout << "{ " << a << ", " << b << ", " << c << " }" << endl; #define print4(a, b, c, d) cout << "{ " << a << ", " << b << ", " << c << ", " << d << " }" << endl; using namespace std; #define int long long const int INF = 1e9 + 228; const int MAXN = 40; map<int, int> dp[MAXN]; int n, k; void slow() { vector<pair<int, int>> v; for (int i = 0; i < n; i++) { int aa, bb; cin >> aa >> bb; v.pb({aa, bb}); } int ans = 0; for (int i = 0; i < n; i++) { dp[i][min(v[i].S, k)]++; for (int j = 0; j < i; j++) { if (v[i].F < v[j].F) continue; //print2(i, j); for (auto to : dp[j]) { dp[i][min(to.F + v[i].S, k)] += to.S; } } } for (int i = 0; i < n; i++) { for (auto to : dp[i]) { if (to.F >= k) { ans += to.S; } } } cout << ans << endl; } signed main() { #ifdef LOCAL FILE; #endif sh; cin >> n >> k; if (n <= 1) { slow(); return 0; } int beg = n / 2; int rs = n - beg; vector<pair<int, int>> v; for (int i = 0; i < n; i++) { int aa, bb; cin >> aa >> bb; v.pb({aa, bb}); } //int ans = 0; for (int i = 0; i < beg; i++) { dp[i][v[i].S]++; for (int j = 0; j < i; j++) { if (v[i].F < v[j].F) continue; //print2(i, j); for (auto to : dp[j]) { dp[i][to.F + v[i].S] += to.S; } } } for (int i = n - 1; i >= beg; i--) { dp[i][v[i].S]++; for (int j = n - 1; j > i; j--) { if (v[i].F > v[j].F) continue; //print2(i, j); for (auto to : dp[j]) { dp[i][to.F + v[i].S] += to.S; } } } int ans = 0; for (int i = 0; i < beg; i++) { for (int j = beg; j < n; j++) { if (v[i].F > v[j].F) { continue; } vector<pair<int, int>> a, b; for (auto to : dp[i]) { a.pb({to.F, to.S}); } for (auto to : dp[j]) { b.pb({to.F, to.S}); } sort(all(a)); sort(all(b)); vector<int> p; p.pb(0); int u = b.size(); for (int i = u - 1; i >= 0; i--) { p.pb(p.back() + b[i].S); } p.pb(p.back()); reverse(all(p)); /*for (auto to : b) { cout << to.F << ' '; } cout << endl;*/ for (auto to : a) { int need = max(0LL, k - to.F); int idx = lower_bound(all(b), mp(need, -INF)) - b.begin(); //print4(i, to.F, j, idx); ans += (to.S * p[idx + 1]); } } } for (int i = 0; i < beg; i++) { for (auto to : dp[i]) { if (to.F >= k) { ans += to.S; } } } for (int i = beg; i < n; i++) { for (auto to : dp[i]) { if (to.F >= k) { ans += to.S; } } } cout << ans << endl; return 0; }

Compilation message (stderr)

san.cpp:2:0: warning: ignoring #pragma comment  [-Wunknown-pragmas]
 #pragma comment(linker,"/stack:200000000")
 
san.cpp: In function 'int main()':
san.cpp:68:6: warning: unused variable 'rs' [-Wunused-variable]
  int rs = n - beg;
      ^~
#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...