Submission #574932

#TimeUsernameProblemLanguageResultExecution timeMemory
574932RealSnakeA Difficult(y) Choice (BOI21_books)C++14
0 / 100
11 ms336 KiB
#include "bits/stdc++.h" using namespace std; #include "books.h" #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set; #define ll long long #define mod 1000000007 int n, ind; ll a; ll pre[100001], arr[100001]; bool dp[100001][11][2]; bool yes; void sol(int j, int k, ll sum, bool b) { if(dp[j][k][b]) return; dp[j][k][b] = 1; if(j == n) { if(!k && sum >= a && sum <= 2 * a) { yes = 1; if(b) arr[ind++] = j; } return; } if(n - j < k || sum + (pre[n] - pre[n - k]) < a || sum + (pre[j + k] - pre[j]) > 2 * a) return; if(b) arr[ind++] = j; sol(j + 1, k, sum, 0); if(yes) return; if(k) sol(j + 1, k - 1, sum + (pre[j + 1] - pre[j]), 1); if(yes) return; if(b) ind--; } void solve(int nn, int k, ll A, int S) { // s = n; n = nn, a = A; for(int i = 1; i <= n; i++) { pre[i] = skim(i); pre[i] += pre[i - 1]; } sol(0, k, 0LL, 0); if(yes) { vector<int> ans; for(int i = 0; i < k; i++) ans.push_back(arr[i]); answer(ans); return; } impossible(); }
#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...