Submission #1071857

#TimeUsernameProblemLanguageResultExecution timeMemory
1071857mickey080929Cultivation (JOI17_cultivation)C++17
80 / 100
2045 ms4880 KiB
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef pair<ll,ll> pll; const ll inf = 2e18; ll R, C; ll N; ll mxl[310][310], mxr[310][310], mxsum[310][310]; ll solve(vector<pll> p, ll H) { vector<pll> upd; ll j = 0; for (ll i=0; i<p.size(); i++) { while (j < p.size() && p[j].first + H <= p[i].first) { upd.push_back({p[j].first + H, -p[j].second}); j ++; } upd.push_back(p[i]); } while (j < p.size()) { upd.push_back({p[j].first + H, -p[j].second}); j ++; } vector<array<ll,4>> save; ll idx1 = 0, idx2 = -1; for (ll i=0; i<upd.size(); i++) { if (upd[i].second > 0) idx2 ++; if (i + 1 != upd.size() && upd[i].first == upd[i+1].first) continue; while (idx1 < N && p[idx1].first + H <= upd[i].first) idx1 ++; if (idx1 > idx2) { save.push_back({upd[i].first, inf, inf, inf}); continue; } save.push_back({upd[i].first, mxsum[idx1][idx2], mxl[idx1][idx2], mxr[idx1][idx2]}); } ll ans = inf; deque<ll> dq[3]; for (ll i=(ll)save.size()-1; i>=0; i--) { for (ll j=0; j<3; j++) { while (!dq[j].empty() && save[dq[j].back()][j+1] <= save[i][j+1]) { dq[j].pop_back(); } while (!dq[j].empty() && save[dq[j].front()][0] > save[i][0] + R - 1) { dq[j].pop_front(); } dq[j].push_back(i); } ans = min(ans, max(save[dq[0].front()][1], save[dq[1].front()][2] + save[dq[2].front()][3])); } return ans; } int main() { ios_base :: sync_with_stdio(false); cin.tie(NULL); cin >> R >> C; cin >> N; vector<pll> p(N); for (ll i=0; i<N; i++) { cin >> p[i].first >> p[i].second; } sort(p.begin(), p.end()); for (ll i=0; i<N; i++) { multiset<ll> s1, s2; for (ll j=i; j<N; j++) { if (!s1.empty()) { auto rit = s1.lower_bound(p[j].second); if (rit != s1.begin()) { auto lit = prev(rit); if (rit != s1.end()) { s2.erase(s2.find(*rit - *lit)); } s2.insert(p[j].second - *lit); } if (rit != s1.end()) { s2.insert(*rit - p[j].second); } } s1.insert(p[j].second); mxl[i][j] = *s1.begin() - 1, mxr[i][j] = C - *s1.rbegin(); mxsum[i][j] = mxl[i][j] + mxr[i][j]; if (!s2.empty()) mxsum[i][j] = *s2.rbegin() - 1; } } vector<ll> cand, U, D; for (ll i=0; i<N; i++) { U.push_back(p[i].first - 1); D.push_back(R - p[i].first); for (ll j=i+1; j<N; j++) { cand.push_back(abs(p[i].first - p[j].first)); } } for (auto &u : U) { for (auto &d : D) { cand.push_back(u + d + 1); } } sort(cand.begin(), cand.end()); cand.erase(unique(cand.begin(), cand.end()), cand.end()); ll ans = inf; for (auto &H : cand) { if (H == 0) continue; ans = min(ans, H - 1 + solve(p, H)); } cout << ans << '\n'; }

Compilation message (stderr)

cultivation.cpp: In function 'll solve(std::vector<std::pair<long long int, long long int> >, ll)':
cultivation.cpp:18:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |  for (ll i=0; i<p.size(); i++) {
      |               ~^~~~~~~~~
cultivation.cpp:19:12: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |   while (j < p.size() && p[j].first + H <= p[i].first) {
      |          ~~^~~~~~~~~~
cultivation.cpp:25:11: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  while (j < p.size()) {
      |         ~~^~~~~~~~~~
cultivation.cpp:31:16: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |  for (ll i=0; i<upd.size(); i++) {
      |               ~^~~~~~~~~~~
cultivation.cpp:33:13: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   if (i + 1 != upd.size() && upd[i].first == upd[i+1].first) continue;
      |       ~~~~~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...