Submission #197132

#TimeUsernameProblemLanguageResultExecution timeMemory
197132PankinDEL13 (info1cup18_del13)C++14
0 / 100
40 ms7396 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> /* #pragma GCC optimize("unroll-loops") #pragma GCC optimize("Ofast") #pragma GCC optimize("-O3") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") */ #define mp make_pair #define ll long long #define ld long double #define pb push_back #define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); #define fs first.first #define sc first.second #define tr second #define getfiles ifstream cin("input.txt"); ofstream cout("output.txt"); #define endl '\n' #define pii pair<int, int> #define tri pair< pair<int, int>, int > #define mt(x, y, z) make_pair(make_pair(x, y), z) const int INF = 2000000005; const ll BIG_INF = 2000000000000000005; const int mod = 1000000007; const int P = 31; const ld PI = 3.141592653589793238462643; const double eps = 1e-9; using namespace std; using namespace __gnu_pbds; bool valid(int x, int y, int n, int m) { return x >= 0 && y >= 0 && x < n && y < m; } mt19937 rng(1999999973); typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set; signed main() { fast_io; int tests; cin >> tests; while(tests--) { int n, q; cin >> n >> q; if (q == 0) { cout << -1 << endl; continue; } vector<int> p(q, 0), block(q + 2, 0); for (int i = 0; i < q; i++) cin >> p[i]; block[0] = p[0] - 1; for (int i = 1; i < q; i++) { block[i] = p[i] - p[i - 1] - 1; } block[q] = n - p[q - 1]; vector< vector< vector<tri> > > dp(q + 1); for (int i = 0; i <= q; i++) { dp[i].resize(block[i] + 1, vector<tri>(2, mt(-1, -1, -1))); } dp[0][block[0]][0] = mt(INF, INF, 0); for (int i = 0; i < q; i++) { for (int j = block[i]; j >= 0; j--) { for (int k = 0; k < 2; k++) { if (dp[i][j][k] == mt(-1, -1, -1)) continue; if (j > 2) dp[i][j - 2][k] = mt(i, j, k); if (j == 2 && k == 1) dp[i][j - 2][k] = mt(i, j, k); if (j <= block[i + 1]) dp[i + 1][block[i + 1] - j][j != 0] = mt(i, j, k); } } } if (dp[q][0][0] == mt(-1, -1, -1) && dp[q][0][1] == mt(-1, -1, -1)) { cout << -1 << endl; continue; } cout << (n - q) / 2 << endl; } return 0; } /* 1 10 4 1 2 5 10 1100100001 */
#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...