Submission #914939

#TimeUsernameProblemLanguageResultExecution timeMemory
914939minhnhatnoeSightseeing in Kyoto (JOI22_kyoto)C++17
10 / 100
2059 ms2904 KiB
#pragma GCC optimize("O3,unroll-loops") #include <bits/stdc++.h> using namespace std; typedef long long ll; const int MAXN = 100000; alignas(1024) ll a[MAXN], b[MAXN], dp[MAXN]; signed main(){ cin.tie(0)->sync_with_stdio(0); int h, w; cin >> h >> w; for (int i=0; i<h; i++){ cin >> a[i]; } for (int j=0; j<w; j++){ cin >> b[j]; } memset(dp, 0x3f, sizeof dp); dp[0] = 0; for (int i=0; i<h-1; i++){ ll v = dp[0]; for (int j=1; j<w; j++){ v = v > dp[j] - a[i] * j ? dp[j] - a[i] * j : v; dp[j] = dp[j] < v + a[i] * j ? dp[j] : v + a[i] * j; } for (int j=0; j<w; j++){ dp[j] += b[j]; } } for (int j=1; j<w; j++){ dp[j] = dp[j] < dp[j-1] + a[h-1] ? dp[j] : dp[j-1] + a[h-1]; } cout << dp[w-1] << "\n"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...