Submission #903952

#	Time	Username	Problem	Language	Result	Execution time	Memory
903952		andrey27_sm	Cultivation (JOI17_cultivation)	C++17	15 / 100	180 ms	612 KiB

cultivation

//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("arch=icelake-server,avx512f,avx512bw,avx512bitalg,bmi,bmi2")

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
constexpr ll mod = 1e9 + 7;

int n,r,c;
vector<ll> grass[41];
ll test(int no,int so) {
    ll min_ea = 0;
    ll min_we = 0;
    ll min_tot = 0;
    for(int i = 0;i < r;i++) {
        vector<ll> items;
        for(int j = max(0,i-no);j <= min(r-1,i+so);j++) {
            for(auto e:grass[j]) {
                items.push_back(e);
            }
        }
        sort(items.begin(),items.end());
        if(items.size() == 0) return 1e15;
        min_ea = max(min_ea,items[0]);
        min_we = max(min_we,c-1-items[items.size()-1]);
        for(int j = 1;j < items.size();j++) {
            min_tot = max(min_tot,items[j]-items[j-1]-1);
        }
    }
    return max(min_ea+min_we,min_tot);
}
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> r >> c >> n;
    for(int i = 0; i < n; i++)
    {
        int x,y;
        cin >> x >> y;
        x--;
        y--;
        grass[x].push_back(y);
    }
    ll best = 1e15;
    for(int no = 0;no < r;no++) {
        for(int so = 0;so+no < r;so++) {
            best = min(best,test(no,so)+no+so);
        }
    }
    cout << best << "\n";
    return 0;
}

Compilation message (stderr)

cultivation.cpp: In function 'll test(int, int)':
cultivation.cpp:27:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         for(int j = 1;j < items.size();j++) {
      |                       ~~^~~~~~~~~~~~~~

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