Submission #960921

#	Time	Username	Problem	Language	Result	Execution time	Memory
960921		danikoynov	Cultivation (JOI17_cultivation)	C++14	5 / 100	1125 ms	604 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[2 * maxc][2 * 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; h ++)
        for (int w = 1; w <= c; w ++)
        {
            for (int i = 0; i < 2 * maxc; i ++)
                for (int j = 0; j < 2 * 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 ++)
                    {
                        used[dx][dy] = 1;
                    }
            }

            bool done = false;
            for (int sx = 0; sx < 2 * r; sx ++)
                for (int sy = 0; sy < 2 * c; sy ++)
                {
                    bool tf = true;

                    for (int i = sx; i < sx + r; i ++)
                        for (int j = sy; j < sy + c; j ++)
                        {
                            if (used[i][j] == 0)
                            {
                              //if (h == 3 && w == 2 && sx == 1 && sy == 2)
                                // 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] << " ";
                }*/
            if (done)
               {

                    ans = min(ans, h + w - 2);
               }
        }
    cout << ans << endl;
}
int main()
{
    solve();
    return 0;
}

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