Submission #476740

#	Time	Username	Problem	Language	Result	Execution time	Memory
476740		prvocislo	Colouring a rectangle (eJOI19_colouring)	C++17	0 / 100	4 ms	1356 KiB

colouring

/*
                                        ██████
            ██████                    ████▒▒████
          ████▒▒████████████████████████████▒▒██
        ██░░████▒▒██░░░░░░░░░░░░░░░░░░░░████▒▒████
      ██░░░░░░████▒▒██░░░░░░░░░░░░██░░░░░░░░████▒▒██
      ██░░░░░░██▒▒██░░░░░░░░░░░░░░░░██░░░░░░░░██▒▒██
    ██░░░░░░██▒▒██░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████
    ██░░░░░░░░██░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██
  ██░░░░░░████░░░░░░██░░░░░░░░░░░░░░██░░░░░░░░  ░░██
  ██░░░░░░██░░░░░░██░░░░░░░░░░░░░░░░██░░      ░░░░░░██
  ██░░░░░░██░░░░░░██░░      ░░    ██  ██░░░░░░░░░░░░██
██░░░░░░░░██░░░░░░██░░░░░░░░██░░░░██  ████░░░░██░░░░██
██░░░░░░░░██░░░░██░░░░░░░░██░░░░██      ██░░░░░░██░░██
██░░░░░░░░██░░░░██░░░░░░██░░░░░░██    ██████░░░░████
██░░░░░░░░██░░████░░░░██████████      ██  ██░░░░████
██░░░░░░░░██░░████████  ████  ██      ▒▒  ██░░░░██
██░░░░░░░░████████▒▒░░    ▒▒          ░░  ██░░████████  ██
██░░░░░░░░████░░██▒▒░░  ▒▒░░          ▒▒  ██░░████  ████  ██
██░░░░░░░░██  ████▒▒░░  ▒▒▒▒              ████░░██  ██    ██
██░░░░░░░░██    ██░░░░                  ████░░░░██      ██
██░░░░░░░░██      ████░░            ██████░░░░░░██    ██
██░░░░░░░░░░██        ██▓▓▓▓▓▓▓▓▓▓░░▓▓  ██░░░░██    ██
██░░░░░░░░░░██      ██    ▓▓▓▓▓▓▓▓░░▓▓██░░████    ██
██░░░░░░░░░░██    ██░░░░██▓▓▓▓▓▓▓▓░░▓▓██████    ████
██░░░░░░░░░░██  ████████░░░░▓▓▓▓░░██░░▓▓██    ██░░░░██
██░░░░░░░░░░░░██████████████░░░░██████░░██  ██░░░░░░██
  ██░░░░░░░░░░████  ████████████████████▓▓██░░░░░░░░██
  ██░░░░░░░░░░██  ████░░░░░░░░░░░░░░░░░░████░░░░░░░░██
    ██░░░░░░░░██      ██████████████████    ██░░░░██
      ██░░░░██      ████████      ██░░██      ████
        ████        ██░░██          ████
                      ██
*/
#include <iostream>
#include <vector>
#include <algorithm>
typedef long long ll;
using namespace std;

const int maxk = 4005;
vector<int> a(maxk), b(maxk), l(maxk), r(maxk);
int m, n;
vector<ll> pfa(maxk), pfb(maxk);
ll suma(int l, int r) { return pfa[r] - pfa[l] + a[l]; }
ll sumb(int l, int r) { return pfb[r] - pfb[l] + b[l]; }
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> m >> n;
	int k = m + n - 1;
    for (int i = 0; i < k; i++)
    {
        cin >> a[i], pfa[i] = a[i];
        if (i >= 2) pfa[i] += pfa[i - 2];
        if (i == 0) l[0] = r[0] = n - 1;
        else if (i <= min(n, m) - 1) l[i] = l[i - 1] - 1, r[i] = r[i - 1] + 1;
        else if (i >= k - min(n, m) + 1) l[i] = l[i - 1] + 1, r[i] = r[i - 1] - 1;
        else l[i] = l[i - 1] + 1, r[i] = r[i - 1] + 1;
    }
    for (int i = 0; i < k; i++)
    {
        cin >> b[i], pfb[i] = b[i];
        if (i >= 2) pfb[i] += pfb[i - 2];
    }
    vector<ll> ans(2, 1e18);
    for (int c = 0; c < 2; c++)
    {
        ans[c] = pfa[((k - 1 - c) / 2) * 2 + c];
        for (int i = c; i < k; i += 2)
        {
            int bl = k, br = -1;
            for (int j = c; j < i; j += 2) 
                bl = min(bl, l[j]), br = max(br, r[j]);
            for (int j = ((k - 1 - c) / 2) * 2 + c; j >= i; j -= 2)
            {
                if (br != -1)
                {
                    ans[c] = min(ans[c], suma(i, j) + sumb(bl, br));
                }
                bl = min(bl, l[j]);
                br = max(br, r[j]);
            }
            ans[c] = min(ans[c], sumb(bl, br));
        }
    }
    cout << ans[0] + ans[1] << "\n";
	return 0;
}

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