Submission #345462

#TimeUsernameProblemLanguageResultExecution timeMemory
345462_aniMoney (IZhO17_money)C++17
45 / 100
3 ms748 KiB
#include <iostream> #include <vector> #include <algorithm> using namespace std; const int N = 302; int dp[N], a[N]; vector<int> s[N]; int main() { int n; cin >> n; for(int i = 0; i < n; i++) { cin >> a[i]; dp[i]=i+1; } for(int i = 0; i < n; i++){ if(i != 0){ s[i] = s[i - 1]; } s[i].push_back(a[i]); sort(s[i].begin(), s[i].end()); } for(int i = 0; i < n; i++){ for(int j = i; j >= 0; j--){ if(j + 1 <= i && a[j] > a[j + 1])break; if(j - 1 < 0){ dp[i] = 1; continue; } auto x = upper_bound(s[j - 1].begin(), s[j - 1].end(),a[j]) - s[j - 1].begin(); if(x == (int)s[j - 1].size() || s[j - 1][x] >= a[i]){ dp[i] = min(dp[i], dp[j - 1] + 1); } } } cout << dp[n - 1]; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...