Submission #1103536

#TimeUsernameProblemLanguageResultExecution timeMemory
1103536stdfloatMoney (IZhO17_money)C++17
0 / 100
1 ms520 KiB
#include <bits/stdc++.h> using namespace std; #define ff first #define ss second #define pii pair<int, int> #define sz(v) (int)(v).size() #define all(v) (v).begin(), (v).end() int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n; cin >> n; vector<int> a(n); for (auto &i : a) { cin >> i; i--; } int mn = INT_MAX; for (int mk = 0; mk < 1 << (n - 1); mk++) { bool tr = true; int pre = -1, cnt = 0; map<int, vector<int>> m; for (int i = 0; i < n && tr; i++) { if (i != n - 1 && !((mk >> i) & 1)) continue; for (int j = pre + 1; j < i && tr; j++) { tr = (a[j] <= a[j + 1]); m[a[j]].push_back(a[j + 1]); } cnt++; pre = i; } if (!tr) continue; set<int> s = {INT_MAX}; for (auto i : m) { for (auto j : i.ss) { if (*s.upper_bound(i.ff) < j) { tr = false; break; } } if (!tr) break; for (auto j : i.ss) s.insert(j); } if (tr) mn = min(mn, cnt); } assert(mn != INT_MAX); cout << mn; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...