Submission #609637

#TimeUsernameProblemLanguageResultExecution timeMemory
609637TigryonochekkSightseeing in Kyoto (JOI22_kyoto)C++17
40 / 100
72 ms33256 KiB
#include <iostream> #include <algorithm> #include <cmath> #include <vector> #include <set> #include <map> #include <string> using namespace std; #define ll long long #define pii pair<int, int> const int A = 1002, N = 1e5 + 2; const ll inf = 1e18 + 49; int h, w; int a[N], b[N]; int fto[A], lto[A]; int fsu[A], lsu[A]; vector<int> toxs, syuns; ll dp[2 * A][2 * A]; int main() { cin >> h >> w; for (int i = 1; i <= h; i++) { cin >> a[i]; } for (int i = 1; i <= w; i++) { cin >> b[i]; } if (h <= 1000 && w <= 1000) { for (int i = 1; i <= h; i++) { for (int j = 1; j <= w; j++) { dp[i][j] = inf; dp[1][1] = 0; if (i > 1) dp[i][j] = min(dp[i][j], dp[i - 1][j] + b[j]); if (j > 1) dp[i][j] = min(dp[i][j], dp[i][j - 1] + a[i]); } } cout << dp[h][w] << endl; } else { for (int i = 1; i <= h; i++) { if (!fto[a[i]]) fto[a[i]] = i; } for (int i = 1; i <= w; i++) { if (!fsu[b[i]]) fsu[b[i]] = i; } for (int i = h; i >= 1; i--) { if (!lto[a[i]]) lto[a[i]] = i; } for (int i = w; i >= 1; i--) { if (!lsu[b[i]]) lsu[b[i]] = i; } for (int i = 1; i <= h; i++) { if (fto[a[i]] == i) toxs.push_back(i); else if (lto[a[i]] == i) toxs.push_back(i); } for (int i = 1; i <= w; i++) { if (fsu[b[i]] == i) syuns.push_back(i); else if (lsu[b[i]] == i) syuns.push_back(i); } int n = toxs.size(), m = syuns.size(); dp[0][0] = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { dp[i][j] = inf; dp[0][0] = 0; if (i) { dp[i][j] = min(dp[i][j], dp[i - 1][j] + b[syuns[j]] * (toxs[i] - toxs[i - 1])); } if (j) { dp[i][j] = min(dp[i][j], dp[i][j - 1] + a[toxs[i]] * (syuns[j] - syuns[j - 1])); } } } cout << dp[n - 1][m - 1] << endl; } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...