Submission #1071203

#TimeUsernameProblemLanguageResultExecution timeMemory
1071203kunzaZa183Cultivation (JOI17_cultivation)C++17
0 / 100
20 ms2652 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); 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); } if(mins > minso + minn) { minso += mins - (minso + minn); } vector<pair<char,int>> extra; for(int i = 0; i <n;i++) { extra.emplace_back('N',max(0,vpii[i].first - minn)); extra.emplace_back('S', max(0, (r - 1) - (vpii[i].first + minso))); } for(int i = 0; i < n;i++) for(int j = i + 1; j < n;j++) if(vpii[i].first + minso < vpii[j].first - minn) { extra.emplace_back('S',(vpii[j].first - minn) - (vpii[i].first + minso)); } 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<<a.first<<" "<<a.second<<"\n"; for(int i = 0; i < n;i++){ int add = vpii[i].first - minn,minus = vpii[i].first + minso + 1; if(a.first =='N') add -= a.second; else minus += 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.second); } cout<<minans<<'\n'; return 0; }

Compilation message (stderr)

cultivation.cpp: In function 'int main()':
cultivation.cpp:65: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]
   65 |   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:123:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |       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...