Submission #635682

#TimeUsernameProblemLanguageResultExecution timeMemory
635682IWTIMSan (COCI17_san)C++14
120 / 120
237 ms10024 KiB
# include <bits/stdc++.h> using namespace std; #define f first #define s second #define int long long #define pii pair <int, int> #define pb push_back const int N = 3e5 + 5; int t,n,a[N],ans,g[N],sum,k; vector <int> v[N]; void find(int pr, int sum, int k) { int le = 0; int ri = (int)v[pr].size() - 1; int pas = ri + 1; while (le <= ri) { int mid = (le + ri) / 2; if (v[pr][mid] + sum >= k) { pas = mid; ri = mid - 1; } else le = mid + 1; } ans += (int)v[pr].size() - pas; } main() { std::ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0); cin>>n>>k; for (int i = 0; i < n; i++) { cin>>a[i]>>g[i]; } for (int i = 1; i < (1<<(n/2)); i++) { int sum = 0, lst = -1, cur = -1, ff = 0; for (int j = 0; j < n/2; j++) { if ((1<<j)&i) { lst = j; sum += g[j]; if (a[j] < cur) ff = 1; cur = a[j]; } } if (ff) continue; ans += (sum >= k); v[lst].pb(sum); } for (int i = 0; i < n; i++) sort(v[i].begin(), v[i].end()); for (int i = 1; i < (1<<(n - n/2)); i++) { int sum = 0, frst = -1,ff = 0, cur = -1; for (int j = n / 2; j < n; j++) { int x = j - n / 2; if ((1<<x)&i) { if (a[j] < cur) ff = 1; if (frst == -1) frst = j; sum += g[j]; cur = a[j]; } } if (ff) continue; ans += (sum >= k); for (int pr = 0; pr < n/2; pr++) { if (a[pr] <= a[frst]) { find(pr,sum, k); } } } cout<<ans<<"\n"; }

Compilation message (stderr)

san.cpp:24:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   24 | main() {
      | ^~~~
#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...