| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 55296 | ksun48 | Cultivation (JOI17_cultivation) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int r, c, n;
vector<pair<int,int> > seeds;
const int INF = 2100100100;
int best = INF;
set<int> tried;
void tryxfast(int x){
if(x < 0 || tried.find(x) != tried.end()){
return;
}
tried.insert(x);
set<int> times;
for(pair<int,int> z : seeds){
times.insert(z.first - x);
times.insert(z.first + 1);
}
vector<int> pos;
map<int,int> idx;
for(int t : times){
idx[t] = pos.size();
pos.push_back(t);
}
vector<int> > ins[pos.size()];
vector<int> > del[pos.size()];
for(pair<int,int> z : seeds){
ins[idx[z.first - x]].push_back(z.second); // ins
del[idx[z.first + 1]].push_back(z.second); // del
}
vector<int> ups;
vector<int> downs;
vector<int> totals;
multiset<int> grass;
grass.insert(-1);
grass.insert(c);
multiset<int> diffs;
diffs.insert(-(c+1));
for(int i = 0; i < pos.size(); i++){
for(int a : ins[i]){
grass.insert(a);
int a1 = *(--grass.find(a));
int a2 = *(++grass.find(a));
diffs.erase(diffs.find(a1-a2));
diffs.insert(a1-a);
diffs.insert(a-a2);
}
for(int a : del[i]){
int a1 = *(--grass.find(a));
int a2 = *(++grass.find(a));
diffs.erase(diffs.find(a1-a));
diffs.erase(diffs.find(a-a2));
diffs.insert(a1-a2);
grass.erase(grass.find(a));
}
totals.push_back( -*diffs.begin() );
ups.push_back( *(++grass.begin()) - 0 );
downs.push_back( c-1 - *(--(--grass.end())) );
}
// two pointers:
int j = 0;
multiset<int> upset;
multiset<int> downset;
multiset<int> totalset;
for(int i = 0; i < pos.size(); i++){
while(j < pos.size() && pos[j] <= pos[i] + r - 1){
upset.insert(-ups[j]);
downset.insert(-downs[j]);
totalset.insert(-totals[j]);
j++;
}
int total = -*totalset.begin();
if(total < c+1){
LL need = max((LL)-*upset.begin() + (LL)-*downset.begin(), (LL)total - 1);
best = (int)min((LL)best, need + x);
}
upset.erase(upset.find(-ups[i]));
downset.erase(downset.find(-downs[i]));
totalset.erase(totalset.find(-totals[i]));
}
}
int main(){
cin.sync_with_stdio(0); cin.tie(0);
cin >> r >> c >> n;
for(int i = 0; i < n; i++){
int s, e;
cin >> s >> e;
s--; e--;
seeds.push_back({s,e});
}
sort(seeds.begin(), seeds.end());
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
tryxfast(seeds[i].first + r-1 - seeds[j].first);
tryxfast(seeds[i].first - 1 - seeds[j].first);
}
}
cout << best << '\n';
}