Submission #870967

#TimeUsernameProblemLanguageResultExecution timeMemory
870967EJIC_B_KEDAXSightseeing in Kyoto (JOI22_kyoto)C++17
40 / 100
2054 ms16608 KiB
#ifdef LOCAL //#define _GLIBCXX_DEBUG #endif #include <bits/stdc++.h> #ifndef LOCAL // #pragma GCC optimize("O3") // #pragma GCC optimize("Ofast") // #pragma GCC optimize("unroll-loops") // #pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt") #endif using namespace std; using ll = long long; using ld = long double; #define x first #define y second #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() mt19937_64 mt(time(0)); void solve(); void init(); int32_t main() { #ifndef LOCAL cin.tie(nullptr)->sync_with_stdio(false); #else freopen("input.txt", "r", stdin); #endif init(); int t = 1; // cin >> t; while (t--) { solve(); } } void init() {} int lovv66; // #define int ll void solve() { int h, w; cin >> h >> w; vector<pair<ll, ll>> a1(h), b1(w), a, b, af, bf, as, bs; for (int i = 0; i < h; i++) { cin >> a1[i].x; a1[i].y = 1; } for (int i = 0; i < w; i++) { cin >> b1[i].x; b1[i].y = 1; } for (int i = 0; i < h; i++) { while (a.size() >= 2) { auto ff = a.back(); a.pop_back(); if (!(a1[i].x <= ff.x && a.back().x <= ff.x)) { a.push_back(ff); break; } else { a.back().y += ff.y; } } a.push_back(a1[i]); } for (int i = 0; i < w; i++) { while (b.size() >= 2) { auto ff = b.back(); b.pop_back(); if (!(b1[i].x <= ff.x && b.back().x <= ff.x)) { b.push_back(ff); break; } else { b.back().y += ff.y; } } b.push_back(b1[i]); } ll ans = 0; h = a.size(); w = b.size(); af.push_back(a[0]); bf.push_back(b[0]); for (int i = 1; i < h; i++) { if (a[i] > a[i - 1]) { as.push_back(a[i]); } else { af.push_back(a[i]); } } for (int i = 1; i < w; i++) { if (b[i] > b[i - 1]) { bs.push_back(b[i]); } else { bf.push_back(b[i]); } } // as.insert(as.begin(), af.back()); // bs.insert(bs.begin(), bf.back()); reverse(all(as)); reverse(all(bs)); as.push_back(af.back()); bs.push_back(bf.back()); for (int i = 0; i < as.size(); i++) { as[i].y = as[(i + 1) % as.size()].y; } for (int i = 0; i < bs.size(); i++) { bs[i].y = bs[(i + 1) % bs.size()].y; } // for (auto i : a) { // cout << i.x << ' '; // } // cout << '\n'; // for (auto i : b) { // cout << i.x << ' '; // } // cout << '\n'; // for (auto i : af) { // cout << i.x << ' '; // } // cout << '\n'; // for (auto i : bf) { // cout << i.x << ' '; // } // cout << '\n'; // for (auto i : as) { // cout << i.x << ' '; // } // cout << '\n'; // for (auto i : bs) { // cout << i.x << ' '; // } // cout << '\n'; // a = af; a.clear(); for (int i = 0; i < af.size(); i++) { while (a.size() >= 2) { auto ff = a.back(); a.pop_back(); if ((ff.x - af[i].x) * a.back().y < (a.back().x - ff.x) * ff.y) { a.push_back(ff); break; } else { a.back().y += ff.y; } } a.push_back(af[i]); } // b = bf; b.clear(); for (int i = 0; i < bf.size(); i++) { while (b.size() >= 2) { auto ff = b.back(); b.pop_back(); if ((ff.x - bf[i].x) * b.back().y < (b.back().x - ff.x) * ff.y) { b.push_back(ff); break; } else { b.back().y += ff.y; } } b.push_back(bf[i]); } h = a.size(); w = b.size(); lovv66 = 1e7 / h; ll dp[2][100100]{}, ax[100100]{}, bx[100100]{}, ay[100100]{}, by[100100]{}; // vector<ll> ax(100100), bx(100100), ay(100100), by(100100); // vector<vector<ll>> dp(2, vector<ll>(w + 1, INT64_MAX)); for (int j = 0; j < w + 1; j++) { dp[0][j] = INT64_MAX; } for (int i = 0; i < h; i++) { ax[i] = a[i].x; ay[i] = a[i].y; } for (int i = 0; i < w; i++) { bx[i] = b[i].x; by[i] = b[i].y; } dp[0][0] = 0; // assert(h <= 3e4 && w <= 3e4); for (int i = 0; i < h; i++) { for (int j = max(0, i - lovv66); j < min(w + 1, i + lovv66 + 10); j++) { dp[1][j] = INT64_MAX; } for (int j = max(0, i - lovv66); j < min(w, i + lovv66); j++) { dp[1][j] = min(dp[1][j], dp[0][j] + bx[j] * ay[i]); dp[0][j + 1] = min(dp[0][j + 1], dp[0][j] + ax[i] * by[j]); } swap(dp[0], dp[1]); } ans += dp[1][w - 1]; // cout << dp[0][w - 1] << '\n'; a.clear(); for (int i = 0; i < as.size(); i++) { while (a.size() >= 2) { auto ff = a.back(); a.pop_back(); if ((ff.x - as[i].x) * a.back().y < (a.back().x - ff.x) * ff.y) { a.push_back(ff); break; } else { a.back().y += ff.y; } } a.push_back(as[i]); } // b = bf; b.clear(); for (int i = 0; i < bs.size(); i++) { while (b.size() >= 2) { auto ff = b.back(); b.pop_back(); if ((ff.x - bs[i].x) * b.back().y < (b.back().x - ff.x) * ff.y) { b.push_back(ff); break; } else { b.back().y += ff.y; } } b.push_back(bs[i]); } h = a.size(); w = b.size(); for (int j = 0; j < w + 1; j++) { dp[0][j] = INT64_MAX; } for (int i = 0; i < h; i++) { ax[i] = a[i].x; ay[i] = a[i].y; } for (int i = 0; i < w; i++) { bx[i] = b[i].x; by[i] = b[i].y; } dp[0][0] = 0; lovv66 = 1e7 / h; // assert(h <= 4e4 && w <= 4e4); for (int i = 0; i < h; i++) { for (int j = max(0, i - lovv66); j < min(w + 1, i + lovv66 + 10); j++) { dp[1][j] = INT64_MAX; } for (int j = max(0, i - lovv66); j < min(w, i + lovv66); j++) { dp[1][j] = min(dp[1][j], dp[0][j] + bx[j] * ay[i]); dp[0][j + 1] = min(dp[0][j + 1], dp[0][j] + ax[i] * by[j]); } swap(dp[0], dp[1]); } ans += dp[1][w - 1]; // cout << dp[0][w - 1] << '\n'; cout << ans << '\n'; }

Compilation message (stderr)

kyoto.cpp: In function 'void solve()':
kyoto.cpp:110:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |     for (int i = 0; i < as.size(); i++) {
      |                     ~~^~~~~~~~~~~
kyoto.cpp:113:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |     for (int i = 0; i < bs.size(); i++) {
      |                     ~~^~~~~~~~~~~
kyoto.cpp:142:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  142 |     for (int i = 0; i < af.size(); i++) {
      |                     ~~^~~~~~~~~~~
kyoto.cpp:157:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  157 |     for (int i = 0; i < bf.size(); i++) {
      |                     ~~^~~~~~~~~~~
kyoto.cpp:202:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  202 |     for (int i = 0; i < as.size(); i++) {
      |                     ~~^~~~~~~~~~~
kyoto.cpp:217:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  217 |     for (int i = 0; i < bs.size(); i++) {
      |                     ~~^~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...