Submission #239527

#TimeUsernameProblemLanguageResultExecution timeMemory
239527FischerK blocks (IZhO14_blocks)C++14
100 / 100
212 ms3636 KiB
/** * code generated by JHelper * More info: https://github.com/AlexeyDmitriev/JHelper * @author Miguel Mini */ #include <string> #include <vector> #include <algorithm> #include <set> #include <map> #include <queue> #include <iostream> #include <sstream> #include <cstdio> #include <cmath> #include <ctime> #include <cstring> #include <stack> #define sz(x) (int)x.size() #define trav(v, x) for (auto v : x) #define re(x, y, z) for (int x=y; x<z; ++x) #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define set_to(x, v) fill(all(x), v) #define eb emplace_back #define lso(x) ((x)&-(x)) #define mset(m ,v) memset(m, v, sizeof(m)) using namespace std; using ll = long long; using ii = pair<int, int>; using vi = vector<int>; using vii = vector<ii>; const int mod = 1e9 + 7; const ll inf = 1.e18; const int maxn = 1e5 + 10; int a[maxn]; ll dp[maxn][2]; class IZHO_14_blocks { public: void solveOne(istream& in, ostream& out) { int n, k; in >> n >> k; re(i, 0, n) { in >> a[i]; } for (int i = 0; i < n; ++i) { dp[i][1] = i == 0 ? a[i] : max(0ll + a[i], dp[i-1][1]); } for (int i = 2; i <= k; ++i) { stack<ll> s1({inf}); stack<ll> s2({inf}); ll temp = inf; for (int j = 0; j < n; ++j) { while (!s1.empty() && s1.top() <= a[j]) { temp = min(temp, s2.top() - s1.top()); s1.pop(); s2.pop(); } s1.push(a[j]); s2.push(min(s2.top(), a[j] + temp)); temp = dp[j][(i&1)^1]; dp[j][i&1] = s2.top(); } } out << dp[n-1][k&1] << endl; } void solve(istream& in, ostream& out) { int testNumber = 1; //in >> testNumber; re(tc, 1, testNumber+1) { //out << "Case #" << tc << ": "; solveOne(in, out); } } }; int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); IZHO_14_blocks solver; std::istream& in(std::cin); std::ostream& out(std::cout); solver.solve(in, out); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...