Submission #951827

#	Time	Username	Problem	Language	Result	Execution time	Memory
951827		EJIC_B_KEDAX	Colouring a rectangle (eJOI19_colouring)	C++17	50 / 100	2062 ms	31876 KiB

colouring

#include <bits/stdc++.h>
#include <random>
 
#ifndef LOCAL
    //#pragma GCC optimize("O3")
    //#pragma GCC optimize("Ofast")
    //#pragma GCC optimize("unroll-loops")
    //#pragma GCC target("avx,avx2,bmi,bmi2,popcnt,lzcnt")
#endif
using namespace std;
using ll = long long;
using dd = double;
using ld = long double;
using uii = unsigned int;
#define x first
#define y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
 
 
void solve();
 
mt19937_64 mt(373);
 
int32_t main() {
#ifdef LOCAL
    freopen("input.in", "r", stdin);
    freopen("output.out", "w", stdout);
#else
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    //freopen("amusing.in", "r", stdin);
    //freopen("amusing.out", "w", stdout);
#endif
    cout << fixed << setprecision(30);
    int tests = 1;
    //cin >> tests;
    while (tests--) {
        solve();
    }
}
 
#define int ll
 
ll get_seg(int l, int r, vector<ll>& pref) {
    if (l > r) {
        return 0;
    }
    return pref[r + 1] - pref[l];
}
 
ll get_seg(pair<int, int>& a, vector<ll>& pref) {
    return pref[a.y + 1] - pref[a.x];
}
 
void solve() {
    int n, m;
    cin >> n >> m;
    vector<int> a[2], b[2];
    for (int i = 0; i < n + m - 1; i++) {
        int c;
        cin >> c;
        b[(m - 1 + i) % 2].push_back(c);
    }
    for (int i = 0; i < n + m - 1; i++) {
        int c;
        cin >> c;
        a[i % 2].push_back(c);
    }
    if (n == 1 && m == 1) {
        cout << min(a[0][0], b[0][0]) << '\n';
        return;
    }
    int sz[2] = {(int)a[0].size(), (int)a[1].size()};
    vector<pair<int, int>> seg[2];
    seg[0].resize(sz[0]);
    seg[1].resize(sz[1]);
    seg[0][0] = {(m - 1) / 2, (m - 1) / 2};
    seg[1][0] = {(m - 2) / 2, m / 2};
    for (int i = 1; i < sz[0]; i++) {
        seg[0][i].x = max((2 * i - m + 1) / 2, seg[0][i - 1].x - 1);
        seg[0][i].y = min((int)b[0].size() - (2 * i - n + 1) / 2 - 1, seg[0][i - 1].y + 1);
    }
    for (int i = 1; i < sz[1]; i++) {
        seg[1][i].x = max((2 * i - m + 2) / 2, seg[1][i - 1].x - 1);
        seg[1][i].y = min((int)b[1].size() - (2 * i - n + 2) / 2 - 1, seg[1][i - 1].y + 1);
    }
    seg[0].emplace_back(0, -1);
    seg[1].emplace_back(0, -1);
    vector<ll> dp[2], pref[2];
    dp[0].resize(sz[0]);
    dp[1].resize(sz[1]);
    pref[0].resize(b[0].size() + 1);
    pref[1].resize(b[1].size() + 1);
    pref[0][0] = 0;
    pref[1][0] = 0;
    for (int i = 0; i < b[0].size(); i++) {
        pref[0][i + 1] = pref[0][i] + b[0][i];
    }
    for (int i = 0; i < b[1].size(); i++) {
        pref[1][i + 1] = pref[1][i] + b[1][i];
    }
//    dp[0][0] = min(get_seg(seg[0][0], pref[0]), (ll) a[0][0]);
//    dp[1][0] = min(get_seg(seg[1][0], pref[1]), (ll) a[1][0]);
    for (int i = 0; i < sz[0]; i++) {
        dp[0][i] = INT64_MAX;
        ll sm = 0;
        int l1 = seg[0][i + 1].x, r1 = seg[0][i + 1].y;
        for (int j = i; j >= 0; j--) {
            if (j > 0) {
                dp[0][i] = min(dp[0][i], sm + get_seg(seg[0][j], pref[0]) - get_seg(max(l1, seg[0][j].x), min(r1, seg[0][j].y), pref[0]) + dp[0][j - 1]);
            } else {
                dp[0][i] = min(dp[0][i], sm + get_seg(seg[0][j], pref[0]) - get_seg(max(l1, seg[0][j].x), min(r1, seg[0][j].y), pref[0]));
            }
            sm += a[0][j];
        }
        dp[0][i] = min(dp[0][i], sm);
        int l = INT32_MAX, r = INT32_MIN;
        for (int j = i; j >= 0; j--) {
            l = min(l, seg[0][j].x);
            r = max(r, seg[0][j].y);
            if (j > 0) {
                dp[0][i] = min(dp[0][i], get_seg(l, r, pref[0]) - get_seg(max(l1, l), min(r1, r), pref[0]) + dp[0][j - 1]);
            } else {
                dp[0][i] = min(dp[0][i], get_seg(l, r, pref[0]) - get_seg(max(l1, l), min(r1, r), pref[0]));
            }
        }
    }
    for (int i = 0; i < sz[1]; i++) {
        dp[1][i] = INT64_MAX;
        ll sm = 0;
        int l1 = seg[1][i + 1].x, r1 = seg[1][i + 1].y;
        for (int j = i; j >= 0; j--) {
            if (j > 0) {
                dp[1][i] = min(dp[1][i], sm + get_seg(seg[1][j], pref[1]) - get_seg(max(l1, seg[1][j].x), min(r1, seg[1][j].y), pref[1]) + dp[1][j - 1]);
            } else {
                dp[1][i] = min(dp[1][i], sm + get_seg(seg[1][j], pref[1]) - get_seg(max(l1, seg[1][j].x), min(r1, seg[1][j].y), pref[1]));
            }
            sm += a[1][j];
        }
        dp[1][i] = min(dp[1][i], sm);
        int l = INT32_MAX, r = INT32_MIN;
        for (int j = i; j >= 0; j--) {
            l = min(l, seg[1][j].x);
            r = max(r, seg[1][j].y);
            if (j > 0) {
                dp[1][i] = min(dp[1][i], get_seg(l, r, pref[1]) - get_seg(max(l1, l), min(r1, r), pref[1]) + dp[1][j - 1]);
            } else {
                dp[1][i] = min(dp[1][i], get_seg(l, r, pref[1]) - get_seg(max(l1, l), min(r1, r), pref[1]));
            }
        }
    }
    cout << dp[0].back() + dp[1].back() << '\n';
}

Compilation message (stderr)

colouring.cpp: In function 'void solve()':
colouring.cpp:97:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for (int i = 0; i < b[0].size(); i++) {
      |                     ~~^~~~~~~~~~~~~
colouring.cpp:100:23: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |     for (int i = 0; i < b[1].size(); i++) {
      |                     ~~^~~~~~~~~~~~~

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