Submission #1247184

#	Time	Username	Problem	Language	Result	Execution time	Memory
1247184		andrei_n	Colouring a rectangle (eJOI19_colouring)	C++20	50 / 100	95 ms	59556 KiB

colouring

#include <bits/stdc++.h>
#ifdef LOCAL
#include <debug.h>
#else
#define debug
#endif // LOCAL
#define int long long

using namespace std;

struct Range
{
    int l, r, c;
};

const int INF = 9999999999999999LL;
int dp[2005][2005];
int best[2005];

int solve(int *a, int *b, int *l, int *r, int n, int m)
{
    debug("solve(n = %, m = %)\n", n, m);
    for(int i=1; i<=n; ++i)
        debug("a[%] = %, l[%] = %, r[%] = %\n", i, a[i], i, l[i], i, r[i]);
    for(int i=1; i<=m; ++i)
        debug("b[%] = %\n", i, b[i]);
    vector<Range> v;
    for(int i=1; i<=n; ++i)
        v.push_back({l[i], r[i], a[i]});
    sort(v.begin(), v.end(), [](const Range &x, const Range &y){return x.l < y.l;});
    vector<vector<Range>> what(m+1);
    for(auto &i : v)
        what[i.r].push_back(i);
    vector<vector<int>> sum(m+1);
    for(int i=1; i<=m; ++i)
    {
        if(what[i].empty()) continue;
        sum[i].assign(what[i].size(), 0);
        sum[i][0] = what[i][0].c;
        for(int j=1; j<what[i].size(); ++j)
            sum[i][j] = sum[i][j-1] + what[i][j].c;
        for(int j=0; j<sum[i].size(); ++j)
            debug("sum[%][%] = %\n", i, j, sum[i][j]);
    }
    debug("ok\n");
    dp[0][0] = 0;
    best[0] = 0;
    for(int i=1; i<=m; ++i)
    {
        best[i] = INF;
        for(int j=0; j<=i; ++j)
        {
            if(i != j)
            {
                dp[i][j] = dp[i-1][j] + b[i];
                auto it = lower_bound(what[i].begin(), what[i].end(), Range({j+1, i, 0}), [](const Range &x, const Range &y){return x.l < y.l;});
                int nr = it - what[i].begin();
                if(--nr >= 0)
                    dp[i][j] += sum[i][nr];
            }
            else
            {
                dp[i][j] = best[i-1] + (sum[i].empty() ? 0 : sum[i].back());
            }
            best[i] = min(best[i], dp[i][j]);
            debug("dp[%][%] = %\n", i, j, dp[i][j]);
        }
    }
    return best[m];
}

int m, n;
int a[2][200005], b[2][200005];
int l[2][200005], r[2][200005];

signed main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>m>>n;
    for(int i=1; i<=m+n-1; ++i)
        cin>>a[i&1][i+1>>1];
    for(int i=1; i<=m+n-1; ++i)
        cin>>b[i&1][i+1>>1];
    int sz[2] = {};
    for(int i=1; i<=m+n-1; ++i)
    {
        int fl, fc;
        if(i <= n)
        {
            fl = 1;
            fc = n - i + 1;
        }
        else
        {
            fl = i - n + 1;
            fc = 1;
        }
        l[i&1][i+1>>1] = fc + fl - 1;
        int oth = min(i, m);
        r[i&1][i+1>>1] = l[i&1][i+1>>1] + (oth - fl) * 2;
        l[i&1][i+1>>1] = (l[i&1][i+1>>1]+1>>1);
        r[i&1][i+1>>1] = (r[i&1][i+1>>1]+1>>1);
        sz[i&1] = (i+1>>1);
    }
    if(n & 1)
        cout<<solve(a[0], b[0], l[0], r[0], sz[0], sz[0]) + solve(a[1], b[1], l[1], r[1], sz[1], sz[1]);
    else
        cout<<solve(a[0], b[1], l[0], r[0], sz[0], sz[1]) + solve(a[1], b[0], l[1], r[1], sz[1], sz[0]);
    return 0;
}

• 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