Submission #1071327

#TimeUsernameProblemLanguageResultExecution timeMemory
1071327kunzaZa183Cultivation (JOI17_cultivation)C++17
0 / 100
447 ms2192 KiB
#include <bits/stdc++.h> using namespace std; signed main() { int r,c; cin>>r>>c; int n; cin>>n; vector<pair<int,int>> vpii(n); for(int i = 0; i < n;i++) { cin>>vpii[i].first>>vpii[i].second; vpii[i].first--, vpii[i].second--; } sort(vpii.begin(),vpii.end()); cerr<<"VPII\n"; for(auto a:vpii) cerr<<a.first<<' '<<a.second<<"\n"; cerr<<"\n"; const int maxn = 300; struct help{ int mine,minw,mins; }; help pcomp[maxn][maxn]; for(int i = 0; i < n;i++) { set<int> si; multiset<int> diff; for(int j = i; j < n; j++) { cerr<<i<<' '<<j<<'\n'; auto [it,trying] = si.insert(vpii[j].second); if(!trying) { pcomp[i][j].minw = *si.begin(); pcomp[i][j].mine = c - 1 - *si.rbegin(); if(!diff.empty()) pcomp[i][j].mins = *diff.rbegin(); continue; } auto bef = it, aft = it; aft++; if(it!=si.begin()) bef--; if(it!=si.begin() && aft != si.end()) { diff.erase(diff.find(*aft - *bef - 1)); } if(it!=si.begin()) diff.insert(*it - *bef - 1); if(aft != si.end()) diff.insert(*aft - *it - 1); pcomp[i][j].minw = *si.begin(); pcomp[i][j].mine = c - 1 - *si.rbegin(); if(!diff.empty()) pcomp[i][j].mins = *diff.rbegin(); } } cerr<<"PCOMP\n"; for(int i = 0; i < n;i++) for(int j =0 ; j < n;j++) cerr<<i<<' '<<j<<' '<<pcomp[i][j].minw<<' '<<pcomp[i][j].mine<<" "<<pcomp[i][j].mins<<"\n"; cerr<<"\n"; int minn = INT_MAX,minso = INT_MAX, mins = 0; for(auto a:vpii) minn = min(minn,a.first), minso = min(minso, r - a.first - 1); for(int i = 0; i < vpii.size() - 1; i++) { mins = max(mins, vpii[i + 1].first - vpii[i].first - 1); } set<pair<int,int>> extra; set<int> extran,extras; extran.insert(0),extras.insert(0); for(int i = 0; i <n;i++) { extran.emplace(max(0,vpii[i].first - minn)); extras.emplace(max(0, (r - 1) - (vpii[i].first + minso))); } set<int> gap; gap.insert(0); for(int i = 0; i < n;i++) for(int j = i + 1; j < n;j++) if(vpii[i].first + minso < vpii[j].first - minn) { gap.emplace((vpii[j].first - minn) - (vpii[i].first + minso)); } for(auto a:extran) { for(auto b:extras) if(a+b >= mins) extra.emplace(a,b); for(auto b:gap) if(b>=a && b >= mins) extra.emplace(a,b-a); } cerr<<"EXTRA\n"; for(auto a:extra) cerr<<a.first <<' '<<a.second<<'\n'; cerr<<"\nN S\n"; cerr<<minn<<' '<<minso<<" "<<mins<<"\n\n"; long long minans = LLONG_MAX; for(auto a:extra) { map<int, vector<int>> mivi; cerr<<"EX "<<a.first<<" "<<a.second<<"\n"; for(int i = 0; i < n;i++){ int add = vpii[i].first - minn - a.first,minus = vpii[i].first + minso + 1 + a.second; add = max(add,0); mivi[add].push_back(i + 1); if(minus < r) mivi[minus].push_back(-(i+1)); } int minw = 0, mine = 0, minsum = 0; set<int> curin; for(auto &a:mivi) { for(auto b:a.second) if(b>0) curin.insert(b - 1); else curin.erase(-b - 1); int sm = *curin.begin(), bg = *curin.rbegin(); cerr<<sm<<' '<<bg<<'\n'; assert((bg - sm + 1) == curin.size()); minw = max(minw, pcomp[sm][bg].minw); mine = max(mine, pcomp[sm][bg].mine); minsum = max(minsum, pcomp[sm][bg].mins); } cerr<<minw<<' '<<mine<<' '<<minsum<<'\n'; minans = min(minans, ((long long)minn) + minso + max(minsum, mine + minw) + a.first + a.second); } cout<<minans<<'\n'; return 0; }

Compilation message (stderr)

cultivation.cpp: In function 'int main()':
cultivation.cpp:72:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   72 |   for(int i = 0; i < vpii.size() - 1; i++) {
      |                  ~~^~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from cultivation.cpp:1:
cultivation.cpp:134:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |       assert((bg - sm + 1) == curin.size());
      |              ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~
#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...