Submission #1071409

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071409		kunzaZa183	Cultivation (JOI17_cultivation)	C++17	60 / 100	2049 ms	16468 KiB

cultivation

#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(vpii[i].first );
    extras.emplace((r - 1) - (vpii[i].first));
  }

  set<int> gap;
  gap.insert(0);
  gap.insert(mins);
  for(int i = 0; i < n;i++)
    for(int j = i + 2; j < n;j++) {
      gap.emplace((vpii[j].first) - (vpii[i].first));
      gap.emplace(max(0,(vpii[j].first) - (vpii[i].first) - 1));
    }
  
  for(auto a:extran) {
    for(auto b:extras)
      if(a+b >= mins && a>= minn && b >= minso)
        extra.emplace(a,b);
  }
  for(auto a:extran)
    for(auto b:gap)
      if(b>=a && b >= mins && a>=minn && b-a >=minso)
        extra.emplace(a,b-a);

  for(auto a:extras)
    for(auto b:gap)
      if(b>=a && b >= mins && b-a>=minn && a >= minso)
        extra.emplace(b - a,a);

  // cerr<<"EXTRA\n";
  // cerr<<extra.size()<<"\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 - a.first,minus = vpii[i].first + 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, max((long long)minsum, (long long)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:143:28: warning: comparison of integer expressions of different signedness: 'int' and 'std::set<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  143 |       assert((bg - sm + 1) == curin.size());
      |              ~~~~~~~~~~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 15 / 15
• Subtask 4: 30 / 30
• Subtask 5: 0 / 20
• Subtask 6: 0 / 20