oj.uz

Submission #961239

# Submission time Handle Problem Language Result Execution time Memory
961239 2024-04-11T18:24:47 Z danikoynov Cultivation (JOI17_cultivation) C++14
80 / 100
 2000 ms 3928 KB 
#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

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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 428 KB Output is correct
16 Correct 0 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 428 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 2 ms 348 KB Output is correct
22 Correct 3 ms 360 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 5 ms 344 KB Output is correct
25 Correct 4 ms 348 KB Output is correct
26 Correct 8 ms 344 KB Output is correct
27 Correct 8 ms 344 KB Output is correct
28 Correct 5 ms 348 KB Output is correct
29 Correct 7 ms 452 KB Output is correct
30 Correct 8 ms 348 KB Output is correct
31 Correct 8 ms 344 KB Output is correct
32 Correct 8 ms 440 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 428 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 2 ms 348 KB Output is correct
22 Correct 3 ms 360 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 5 ms 344 KB Output is correct
25 Correct 4 ms 348 KB Output is correct
26 Correct 8 ms 344 KB Output is correct
27 Correct 8 ms 344 KB Output is correct
28 Correct 5 ms 348 KB Output is correct
29 Correct 7 ms 452 KB Output is correct
30 Correct 8 ms 348 KB Output is correct
31 Correct 8 ms 344 KB Output is correct
32 Correct 8 ms 440 KB Output is correct
33 Correct 1 ms 344 KB Output is correct
34 Correct 5 ms 348 KB Output is correct
35 Correct 11 ms 464 KB Output is correct
36 Correct 8 ms 348 KB Output is correct
37 Correct 8 ms 452 KB Output is correct
38 Correct 11 ms 348 KB Output is correct
39 Correct 8 ms 456 KB Output is correct
40 Correct 8 ms 348 KB Output is correct
41 Correct 3 ms 348 KB Output is correct
42 Correct 6 ms 348 KB Output is correct
43 Correct 7 ms 460 KB Output is correct
44 Correct 8 ms 348 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 8 ms 348 KB Output is correct
3 Correct 9 ms 344 KB Output is correct
4 Correct 8 ms 348 KB Output is correct
5 Correct 9 ms 348 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 8 ms 348 KB Output is correct
9 Correct 4 ms 348 KB Output is correct
10 Correct 9 ms 348 KB Output is correct
11 Correct 9 ms 348 KB Output is correct
12 Correct 9 ms 348 KB Output is correct
13 Correct 2 ms 344 KB Output is correct
14 Correct 4 ms 348 KB Output is correct
15 Correct 2 ms 348 KB Output is correct
16 Correct 8 ms 344 KB Output is correct
17 Correct 9 ms 348 KB Output is correct
18 Correct 4 ms 472 KB Output is correct
19 Correct 8 ms 600 KB Output is correct
20 Correct 8 ms 492 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 348 KB Output is correct
2 Correct 8 ms 348 KB Output is correct
3 Correct 9 ms 344 KB Output is correct
4 Correct 8 ms 348 KB Output is correct
5 Correct 9 ms 348 KB Output is correct
6 Correct 3 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 8 ms 348 KB Output is correct
9 Correct 4 ms 348 KB Output is correct
10 Correct 9 ms 348 KB Output is correct
11 Correct 9 ms 348 KB Output is correct
12 Correct 9 ms 348 KB Output is correct
13 Correct 2 ms 344 KB Output is correct
14 Correct 4 ms 348 KB Output is correct
15 Correct 2 ms 348 KB Output is correct
16 Correct 8 ms 344 KB Output is correct
17 Correct 9 ms 348 KB Output is correct
18 Correct 4 ms 472 KB Output is correct
19 Correct 8 ms 600 KB Output is correct
20 Correct 8 ms 492 KB Output is correct
21 Correct 718 ms 900 KB Output is correct
22 Correct 1135 ms 1156 KB Output is correct
23 Correct 1153 ms 1176 KB Output is correct
24 Correct 896 ms 1164 KB Output is correct
25 Correct 1096 ms 1368 KB Output is correct
26 Correct 326 ms 776 KB Output is correct
27 Correct 1061 ms 1164 KB Output is correct
28 Correct 1089 ms 1160 KB Output is correct
29 Correct 1092 ms 1160 KB Output is correct
30 Correct 1096 ms 1164 KB Output is correct
31 Correct 1133 ms 1168 KB Output is correct
32 Correct 1039 ms 1132 KB Output is correct
33 Correct 962 ms 1164 KB Output is correct
34 Correct 1041 ms 1160 KB Output is correct
35 Correct 1042 ms 1160 KB Output is correct
36 Correct 934 ms 1160 KB Output is correct

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 428 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 1 ms 348 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 2 ms 348 KB Output is correct
22 Correct 3 ms 360 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 5 ms 344 KB Output is correct
25 Correct 4 ms 348 KB Output is correct
26 Correct 8 ms 344 KB Output is correct
27 Correct 8 ms 344 KB Output is correct
28 Correct 5 ms 348 KB Output is correct
29 Correct 7 ms 452 KB Output is correct
30 Correct 8 ms 348 KB Output is correct
31 Correct 8 ms 344 KB Output is correct
32 Correct 8 ms 440 KB Output is correct
33 Correct 1 ms 344 KB Output is correct
34 Correct 5 ms 348 KB Output is correct
35 Correct 11 ms 464 KB Output is correct
36 Correct 8 ms 348 KB Output is correct
37 Correct 8 ms 452 KB Output is correct
38 Correct 11 ms 348 KB Output is correct
39 Correct 8 ms 456 KB Output is correct
40 Correct 8 ms 348 KB Output is correct
41 Correct 3 ms 348 KB Output is correct
42 Correct 6 ms 348 KB Output is correct
43 Correct 7 ms 460 KB Output is correct
44 Correct 8 ms 348 KB Output is correct
45 Correct 3 ms 348 KB Output is correct
46 Correct 8 ms 348 KB Output is correct
47 Correct 9 ms 344 KB Output is correct
48 Correct 8 ms 348 KB Output is correct
49 Correct 9 ms 348 KB Output is correct
50 Correct 3 ms 348 KB Output is correct
51 Correct 1 ms 348 KB Output is correct
52 Correct 8 ms 348 KB Output is correct
53 Correct 4 ms 348 KB Output is correct
54 Correct 9 ms 348 KB Output is correct
55 Correct 9 ms 348 KB Output is correct
56 Correct 9 ms 348 KB Output is correct
57 Correct 2 ms 344 KB Output is correct
58 Correct 4 ms 348 KB Output is correct
59 Correct 2 ms 348 KB Output is correct
60 Correct 8 ms 344 KB Output is correct
61 Correct 9 ms 348 KB Output is correct
62 Correct 4 ms 472 KB Output is correct
63 Correct 8 ms 600 KB Output is correct
64 Correct 8 ms 492 KB Output is correct
65 Correct 718 ms 900 KB Output is correct
66 Correct 1135 ms 1156 KB Output is correct
67 Correct 1153 ms 1176 KB Output is correct
68 Correct 896 ms 1164 KB Output is correct
69 Correct 1096 ms 1368 KB Output is correct
70 Correct 326 ms 776 KB Output is correct
71 Correct 1061 ms 1164 KB Output is correct
72 Correct 1089 ms 1160 KB Output is correct
73 Correct 1092 ms 1160 KB Output is correct
74 Correct 1096 ms 1164 KB Output is correct
75 Correct 1133 ms 1168 KB Output is correct
76 Correct 1039 ms 1132 KB Output is correct
77 Correct 962 ms 1164 KB Output is correct
78 Correct 1041 ms 1160 KB Output is correct
79 Correct 1042 ms 1160 KB Output is correct
80 Correct 934 ms 1160 KB Output is correct
81 Execution timed out 2029 ms 3928 KB Time limit exceeded
82 Halted 0 ms 0 KB -