Submission #1226496

#TimeUsernameProblemLanguageResultExecution timeMemory
1226496PenguinsAreCuteCultivation (JOI17_cultivation)C++17
35 / 100
2095 ms16280 KiB
#include <bits/stdc++.h> using namespace std; int main() { int n, x0, y0; cin >> x0 >> y0 >> n; int a[n], b[n]; for(int i=0;i<n;i++) cin >> a[i] >> b[i]; vector<int> xminus = {0}, yminus = {0}; for(int i=0;i<n;i++) { xminus.push_back(a[i]-1); yminus.push_back(b[i]-1); } long long ans = 4e9; for(auto x1: xminus) for(auto y1: yminus) { vector<int> specX = {x0+x1}, specY = {y0+y1}; for(int i=0;i<n;i++) { if(a[i]-x1-1 >= 1) specX.push_back(a[i]-1); if(b[i]-y1-1 >= 1) specY.push_back(b[i]-1); } vector<pair<int,int>> cond; for(auto xs: specX) for(auto ys: specY) { pair<int,int> pts[n]; for(int i=0;i<n;i++) { if(a[i] <= xs && b[i] <= ys) pts[i] = {xs-a[i],ys-b[i]}; else pts[i]={2e9,2e9}; } sort(pts,pts+n); int pmin = 2e9; cond.push_back({pts[0].first,2e9}); for(int i=0;i<n;i++) { pmin = min(pmin, pts[i].second); cond.push_back({(i==n-1?2e9:pts[i+1].first),pmin}); } } cond.push_back({2e9,y1}); cond.push_back({x1,2e9}); sort(cond.begin(),cond.end()); int sz = cond.size(); for(int i=sz-1;i--;) cond[i].second = max(cond[i].second, cond[i+1].second); for(int i=1;i<sz;i++) ans = min(ans, 0LL+cond[i-1].first+cond[i].second); } cout << ans; }
#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...