Submission #1233764

#	Time	Username	Problem	Language	Result	Execution time	Memory
1233764		jonatas57	Colouring a rectangle (eJOI19_colouring)	C++20	10 / 100	92 ms	16028 KiB

colouring

#include <bits/stdc++.h>

using namespace std;

typedef long long      ll;
typedef vector<int>    vi;
typedef vector<bool>   vb;
typedef pair<int, int> ii;

const int INF = 0x3f3f3f3f;
const ll  INFLL = 0x3f3f3f3f3f3f3f3fll;

#define each(x, s)  for (auto& x : s)
#define loop(x)     for (int i = 0;i < x;i++)
#define vloop(v, x) for (int v = 0;v < x;v++)
#define iter(a)     a.begin(), a.end()
#define riter(a)    a.rbegin(), a.rend()
#define endl        "\n"

int main() {
  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  
  int m, n;
  cin >> n >> m;
  int d = n + m - 1;
  vector<ll> a(d), b(d);
  each(x, b) cin >> x;
  each(x, a) cin >> x;
  vector<tuple<int, int, ll>> is;
  loop(d) {
    int minr = max(0, i - m + 1);
    int maxr = min(i, n - 1);
    int maxc = i - minr;
    int minc = i - maxr;
    is.emplace_back(minr - maxc + m - 1, maxr - minc + m - 1, a[i]);
  }
  sort(iter(is));

  loop(d - 2) b[i + 2] += b[i];
  auto get = [&] (int l, int r) { return b[r] - (l - 2 >= 0 ? b[l - 2] : 0); };

  vector<ll> dp(d + 1, 0);
  int b0 = -2, b1 = -1;
  loop(d) {
    auto& [l, r, x] = is[i];
    ll y = get(max(l, i & 1 ? b1 : b0), r);
    if (x <= y) dp[i + 1] = dp[i] + x;
    else {
      dp[i + 1] = dp[i] + y;
      b1 = r;
    }
    swap(b0, b1);
  }
  cout << dp[d] << endl;
  return 0;
}

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