Submission #961239

#	Time	Username	Problem	Language	Result	Execution time	Memory
961239		danikoynov	Cultivation (JOI17_cultivation)	C++14	80 / 100	2029 ms	3928 KiB

cultivation

#include <bits/stdc++.h>
#define endl '\n'

using namespace std;
typedef long long ll;

const ll maxn = 310;

ll n, r, c;
ll x[maxn], y[maxn];

ll used[maxn];

struct data
{

    ll atl_lf = 0, atl_rf = 0, atl_sum = 0;
    data(ll _atl_lf = 0, ll _atl_rf = 0, ll _atl_sum = 0)
    {
        atl_lf = _atl_lf;
        atl_rf = _atl_rf;
        atl_sum = _atl_sum;
    }
};

int ridx[maxn];
bool cmp(int id1, int id2)
{
    return y[id1] < y[id2];
}

void solve()
{
    cin >> r >> c;
    cin >> n;
    for (ll i = 1; i <= n; i ++)
        cin >> x[i] >> y[i];
    for (int i = 1; i <= n; i ++)
        ridx[i] = i;
    sort(ridx + 1, ridx + n + 1, cmp);
    int x1[maxn], y1[maxn];
    for (int i = 1; i <= n; i ++)
    {
        x1[i] = x[ridx[i]];
        y1[i] = y[ridx[i]];
    }
    for (int i = 1; i <= n; i ++)
    {
        x[i] = x1[i];
        y[i] = y1[i];
    }

    ll res = r + c - 2;
    set < ll > set_x;
    for (ll i = 1; i <= n; i ++)
        set_x.insert(x[i] - 1);

    set < ll > pos_sum;
    for (ll dw : set_x)
    {
        for (int i = 1; i <= n; i ++)
            pos_sum.insert(r - x[i] + dw);
    }

    for (int i = 1; i <= n; i ++)
        for (int j = 1; j <= n; j ++)
            if (x[i] < x[j])
                pos_sum.insert(x[j] - x[i] - 1);

                int cnt = 0;
    for (ll up : pos_sum)
    {

        //cnt ++;
        //cout << cnt << endl;
        set < ll > rel;
        for (ll i = 1; i <= n; i ++)
        {
            rel.insert(x[i]);
            rel.insert(x[i] + up + 1);
        }
        unordered_map < ll, data > tk;

        for (ll i : rel)
        {

            ll atl_sum = 0;
            ll atl_lf = 0;
            ll atl_rf =  0;

            ll last = -1e9;
            for (ll j = 1; j <= n; j ++)
            {
                if (x[j] <= i && x[j] + up >= i)
                {
                    if (last == -1e9)
                        atl_lf = y[j] - 1;
                    atl_rf = c - y[j];
                    if (last != -1e9)
                        atl_sum = max(atl_sum, y[j] - last - 1);
                    last = y[j];
                }
            }

            if (last == -1e9)
            {

                tk[i] = data(4e9, 4e9, 4e9);
                break;
            }
            tk[i] = data(atl_lf, atl_rf, atl_sum);
        }

        vector < ll > p;
        vector < data > dt;
        for (ll cur : rel)
        {
            p.push_back(cur);
            dt.push_back(tk[cur]);
        }

        int sz = p.size();
        for (int i = 0; i < sz; i ++)
        {
            if (tk[p[i]].atl_lf == 4e9)
                continue;
            ll atl_lf = 0, atl_rf = 0, atl_sum = 0;
            bool el = false;

            for (int j = i; j < sz; j ++)
            {

                if (p[j] >= p[i] + r)
                {
                    el = true;
                    break;
                }
                atl_lf = max(atl_lf, dt[j].atl_lf);
                atl_rf = max(atl_rf, dt[j].atl_rf);
                atl_sum = max(atl_sum, dt[j].atl_sum);

                if (p[j] == p[i] + r - 1)
                {
                    el = true;
                    break;
                }
            }
            if (!el)
                break;
            res = min(res, up + max(atl_lf + atl_rf, atl_sum));
        }
        ///res = min(res, up + dw + max(atl_sum, atl_lf + atl_rf));

    }

    cout << res << endl;
}
int main()
{
    solve();
    return 0;
}
/**
1000000000 1000000000
100
687499990 187500017
691054532 301146309
937499988 312500002
687499994 937500007
579878939 781071766
187500018 562500000
187500009 937500018
562499999 562500008
562499985 687499991
562500019 937500016
62499982 562499999
937500012 812500017
62499989 687500003
812499999 937500017
62499984 812500021
937500015 437500007
312500018 937500014
310036583 458285811
437500003 562500008
187500017 62500019
187499985 312499998
551496441 203279853
562499982 187499989
385303681 659168721
687499993 687499989
937499996 62499981
62500001 187500016
812499985 812500019
215537495 587684728
687499983 62499990
312499984 62499994
437500005 687499996
562499985 437500006
387044421 605121137
651037194 233648487
562499997 812500014
812500008 62500017
812500006 437499986
756329791 763987426
339496512 78316611
197312044 768557064
62500007 62499998
62499999 312499992
62499998 437499983
937500012 687500008
268334702 842311165
459996228 460720267
524391767 192601086
823409986 317268352
146104556 706720412
437500014 937499998
437499996 62499999
687500013 562500010
683723088 137815207
312499988 562499983
937500008 187499988
312499983 312500011
312499996 437500008
269415213 79920022
565728845 553063446
437500007 312500010
312499989 687499999
892265260 697335606
437500014 812500003
433841809 376362078
562500021 62500006
687500004 312500004
84457580 4066978
437499989 187500014
562499991 312499996
390328103 84288188
312499989 187500012
312500000 812499993
187499988 812500020
187500005 437500012
187499997 187500016
175638635 223798743
937500001 562499987
687499989 812500019
216905502 669638502
160478500 315332550
687500004 437499994
128358363 704990066
812499988 687499999
194084159 334597203
812500007 312500001
474426716 207645837
62499983 937500018
972563160 513965874
930181948 227235337
35912372 755457475
138588828 121235235
937500015 937499996
812499982 187500011
187499994 687500015
437500011 437500017
791201952 736399743
812499994 562500003
435712551 60736620
141083074 419107650


*/

Compilation message (stderr)

cultivation.cpp: In function 'void solve()':
cultivation.cpp:67:13: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
   67 |             if (x[i] < x[j])
      |             ^~
cultivation.cpp:70:17: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
   70 |                 int cnt = 0;
      |                 ^~~
cultivation.cpp:70:21: warning: unused variable 'cnt' [-Wunused-variable]
   70 |                 int cnt = 0;
      |                     ^~~

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