Submission #548155

#TimeUsernameProblemLanguageResultExecution timeMemory
548155jesus_coconutSightseeing in Kyoto (JOI22_kyoto)C++17
40 / 100
693 ms1048576 KiB
#include <bits/stdc++.h> #define pb push_back using namespace std; using ll = long long; int h, w; vector<int> a, b; vector<int> ca, cb; void load() { cin >> h >> w; ca.pb(1), cb.pb(1); for (int i = 0; i < h; ++i) { int na; cin >> na; while (a.size() >= 2 && a[a.size() - 2] <= a.back() && na <= a.back()) { a.pop_back(); ca[ca.size() - 2] += ca.back(); ca.pop_back(); } a.push_back(na); ca.pb(1); } for (int i = 0; i < w; ++i) { int na; cin >> na; while (b.size() >= 2 && b[b.size() - 2] <= b.back() && na <= b.back()) { b.pop_back(); cb[cb.size() - 2] += cb.back(); cb.pop_back(); } b.push_back(na); cb.pb(1); } h = size(a); w = size(b); } ll inf = 1ll << 58; void slowSolve() { int dh = h + 10; int dw = w + 10; ll dp[dh][dw]; for (int i = 0; i < dh; ++i) { for (int j = 0; j < dw; ++j) dp[i][j] = inf; } dp[1][1] = 0; for (int i = 1; i <= h; ++i) { for (int j = 1; j <= w; ++j) { dp[i][j] = min({dp[i][j], dp[i-1][j] + 1ll * ca[i - 1] * b[j-1], dp[i][j-1] + 1ll * cb[j - 1] * a[i-1]}); } } cout << dp[h][w] << '\n'; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); load(); slowSolve(); return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...