oj.uz

Submission #476740

# Submission time Handle Problem Language Result Execution time Memory
476740 2021-09-28T12:20:59 Z prvocislo Colouring a rectangle (eJOI19_colouring) C++17
0 / 100
 4 ms 1356 KB 
/*
                                        ██████
            ██████                    ████▒▒████
          ████▒▒████████████████████████████▒▒██
        ██░░████▒▒██░░░░░░░░░░░░░░░░░░░░████▒▒████
      ██░░░░░░████▒▒██░░░░░░░░░░░░██░░░░░░░░████▒▒██
      ██░░░░░░██▒▒██░░░░░░░░░░░░░░░░██░░░░░░░░██▒▒██
    ██░░░░░░██▒▒██░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░████
    ██░░░░░░░░██░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░░██
  ██░░░░░░████░░░░░░██░░░░░░░░░░░░░░██░░░░░░░░  ░░██
  ██░░░░░░██░░░░░░██░░░░░░░░░░░░░░░░██░░      ░░░░░░██
  ██░░░░░░██░░░░░░██░░      ░░    ██  ██░░░░░░░░░░░░██
██░░░░░░░░██░░░░░░██░░░░░░░░██░░░░██  ████░░░░██░░░░██
██░░░░░░░░██░░░░██░░░░░░░░██░░░░██      ██░░░░░░██░░██
██░░░░░░░░██░░░░██░░░░░░██░░░░░░██    ██████░░░░████
██░░░░░░░░██░░████░░░░██████████      ██  ██░░░░████
██░░░░░░░░██░░████████  ████  ██      ▒▒  ██░░░░██
██░░░░░░░░████████▒▒░░    ▒▒          ░░  ██░░████████  ██
██░░░░░░░░████░░██▒▒░░  ▒▒░░          ▒▒  ██░░████  ████  ██
██░░░░░░░░██  ████▒▒░░  ▒▒▒▒              ████░░██  ██    ██
██░░░░░░░░██    ██░░░░                  ████░░░░██      ██
██░░░░░░░░██      ████░░            ██████░░░░░░██    ██
██░░░░░░░░░░██        ██▓▓▓▓▓▓▓▓▓▓░░▓▓  ██░░░░██    ██
██░░░░░░░░░░██      ██    ▓▓▓▓▓▓▓▓░░▓▓██░░████    ██
██░░░░░░░░░░██    ██░░░░██▓▓▓▓▓▓▓▓░░▓▓██████    ████
██░░░░░░░░░░██  ████████░░░░▓▓▓▓░░██░░▓▓██    ██░░░░██
██░░░░░░░░░░░░██████████████░░░░██████░░██  ██░░░░░░██
  ██░░░░░░░░░░████  ████████████████████▓▓██░░░░░░░░██
  ██░░░░░░░░░░██  ████░░░░░░░░░░░░░░░░░░████░░░░░░░░██
    ██░░░░░░░░██      ██████████████████    ██░░░░██
      ██░░░░██      ████████      ██░░██      ████
        ████        ██░░██          ████
                      ██
*/
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 1356 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 4 ms 1356 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #7
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Incorrect 1 ms 332 KB Output isn't correct
6 Halted 0 ms 0 KB -