oj.uz

Submission #999375

# Submission time Handle Problem Language Result Execution time Memory
999375 2024-06-15T11:42:11 Z AdamGS Cultivation (JOI17_cultivation) C++17
5 / 100
 2000 ms 440 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const ll INF=2e9+7;
const int LIM=307;
pair<ll,ll>T[LIM];
ll R, C, n;
ll solveab(ll a, ll b) {
  set<pair<ll,ll>>A;
  multiset<ll>B;
  vector<pair<ll,ll>>V;
  vector<ll>odw(n);
  rep(i, n) V.pb({max(1ll, T[i].st-a), i});
  rep(i, n) V.pb({min(R+1, T[i].st+b+1), i});
  sort(all(V));
  ll c=0, d=0, cpd=0, lst=1;
  for(auto i : V) {
    if(i.st!=lst) {
      if(A.size()) {
        auto it=A.begin();
        auto p=*it;
        c=max(c, p.st-1);
        it=A.end(); --it;
        p=*it;
        d=max(d, C-p.st);
      }
      if(B.size()) {
        auto it=B.end(); --it;
        ll p=*it;
        cpd=max(cpd, p);
      }
      lst=i.st;
    }
    if(!odw[i.nd]) {
      odw[i.nd]=1;
      if(A.size()) {
        ll lewo=0, prawo=C+1;
        auto it=A.lower_bound({T[i.nd].nd, i.nd});
        if(it!=A.end()) {
          auto p=*it;
          prawo=p.st;
        }
        if(it!=A.begin()) {
          --it;
          auto p=*it;
          lewo=p.st;
        }
        if(lewo!=0 && prawo!=C+1) B.erase(B.find(prawo-lewo-1));
        if(lewo!=0) B.insert(T[i.nd].nd-lewo-1);
        if(prawo!=C+1) B.insert(prawo-T[i.nd].nd-1);
      }
      A.insert({T[i.nd].nd, i.nd});
    } else {
      A.erase({T[i.nd].nd, i.nd});
      if(A.size()) {
        ll lewo=0, prawo=C+1;
        auto it=A.lower_bound({T[i.nd].nd, i.nd});
        if(it!=A.end()) {
          auto p=*it;
          prawo=p.st;
        }
        if(it!=A.begin()) {
          --it;
          auto p=*it;
          lewo=p.st;
        }
        if(lewo!=0 && prawo!=C+1) B.insert(prawo-lewo-1);
        if(lewo!=0) B.erase(B.find(T[i.nd].nd-lewo-1));
        if(prawo!=C+1) B.erase(B.find(prawo-T[i.nd].nd-1));
      }
    }
  }
  return a+b+max(c+d, cpd);
}
ll solvea(ll a) {
  vector<ll>A;
  rep(i, n) A.pb(T[i].st);
  sort(all(A));
  ll b=R-A[n-1], apb=0;
  rep(i, n-1) apb=max(apb, A[i+1]-A[i]-1);
  ll ans=INF;
  rep(i, n) {
    ll x=R-T[i].st;
    if(x>=b && a+x>=apb) ans=min(ans, solveab(a, x));
  }
  rep(i, n) rep(j, i) {
    ll x=abs(T[i].st-T[j].st)-1;
    if(x>=b && a+x>=apb) ans=min(ans, solveab(a, x));
  }
  return ans;
}
ll solve() {
  ll ans=INF;
  rep(i, n) ans=min(ans, solvea(T[i].st-1));
  return ans;
}
int main() {
  ios_base::sync_with_stdio(0); cin.tie(0);
  cin >> R >> C >> n;
  rep(i, n) cin >> T[i].st >> T[i].nd;
  ll ans=INF;
  rep(i, 4) {
    ans=min(ans, solve());
    rep(j, n) T[j]={C-T[j].nd+1, T[j].st};
    swap(R, C);
  }
  cout << ans << '\n';
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 4 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 16 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 4 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 16 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 99 ms 348 KB Output is correct
18 Execution timed out 2054 ms 344 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #3
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 4 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 16 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 99 ms 348 KB Output is correct
18 Execution timed out 2054 ms 344 KB Time limit exceeded
19 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 348 KB Output is correct
2 Correct 140 ms 440 KB Output is correct
3 Correct 188 ms 440 KB Output is correct
4 Correct 127 ms 348 KB Output is correct
5 Correct 165 ms 348 KB Output is correct
6 Correct 155 ms 348 KB Output is correct
7 Correct 91 ms 348 KB Output is correct
8 Correct 55 ms 344 KB Output is correct
9 Correct 98 ms 440 KB Output is correct
10 Incorrect 146 ms 348 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 348 KB Output is correct
2 Correct 140 ms 440 KB Output is correct
3 Correct 188 ms 440 KB Output is correct
4 Correct 127 ms 348 KB Output is correct
5 Correct 165 ms 348 KB Output is correct
6 Correct 155 ms 348 KB Output is correct
7 Correct 91 ms 348 KB Output is correct
8 Correct 55 ms 344 KB Output is correct
9 Correct 98 ms 440 KB Output is correct
10 Incorrect 146 ms 348 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 4 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 16 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 99 ms 348 KB Output is correct
18 Execution timed out 2054 ms 344 KB Time limit exceeded
19 Halted 0 ms 0 KB -