Submission #960934

#	Time	Username	Problem	Language	Result	Execution time	Memory
960934		danikoynov	Cultivation (JOI17_cultivation)	C++14	15 / 100	482 ms	600 KiB

cultivation

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

using namespace std;
typedef long long ll;

const int maxn = 310, maxc = 42;

int n, r, c;
int used[4 * maxc][4 * maxc];
int x[maxn], y[maxn];

void solve()
{
    cin >> r >> c;
    cin >> n;
    for (int i = 1; i <= n; i ++)
        cin >> x[i] >> y[i];
    int ans = r + c - 2;
    for (int h = 1; h <= r * 2; h ++)
        for (int w = 1; w <= c * 2; w ++)
        {
            for (int i = 0; i < 4 * maxc; i ++)
                for (int j = 0; j < 4 * maxc; j ++)
                    used[i][j] = 0;

            for (int i = 1; i <= n; i ++)
            {

                for (int dx = x[i]; dx < x[i] + h; dx ++)
                    for (int dy = y[i]; dy < y[i] + w; dy ++)
                    {
                        ///assert(dx < 2 * maxc && dy < 2 * maxc);
                        used[dx][dy] = 1;
                    }
            }

            bool done = false;
            for (int sx = 0; sx < maxc && !done; sx ++)
                for (int sy = 0; sy < maxc; sy ++)
                {
                    bool tf = true;

                    for (int i = sx; i < sx + r && tf; i ++)
                        for (int j = sy; j < sy + c; j ++)
                        {
                            ///assert(i < 2 * maxc && j <2 * maxc);
                            if (used[i][j] == 0)
                            {
                                //if (h == 25 && w == 29)
                                //cout << sx << " : " << sy << " " << i << " " << j << endl;
                                tf = false;
                                break;
                            }
                        }

                    if (tf)
                    {
                        done = true;
                        break;
                    }
                }

            /*if (h == 3 && w == 2)
            {
                 for (int i = 1; i <= 8; i ++, cout << endl)
                     for (int j = 1; j <= 8; j ++)
                     cout << used[i][j] << " ";
            }*/
            /**cout <<"------------------------------" << endl;
            if (h == 2)
                exit(0);
            for (int i = 0; i < 2 * r; i ++, cout << endl)
                     for (int j = 0; j < 2 * c; j ++)
                     cout << used[i][j] << " ";*/
            if (done)
            {


                ///cout << h << " : " << w << endl;

                //exit(0);
                ans = min(ans, h + w - 2);
                break;
            }
        }
    cout << ans << endl;
}
int main()
{
    solve();
    return 0;
}
/**
40 30
50
19 20
18 16
34 28
5 8
28 21
24 13
7 1
28 23
28 18
12 6
3 6
18 8
40 27
22 19
23 22
8 6
9 12
16 10
27 25
26 19
4 9
40 26
21 22
10 8
5 2
30 25
12 12
3 1
24 14
5 3
4 8
19 9
21 16
6 3
38 29
27 20
37 25
36 24
22 20
29 26
30 19
16 14
3 3
39 25
5 7
20 15
13 12
33 30
27 16
25 14

*/

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