Submission #1195959

#	Time	Username	Problem	Language	Result	Execution time	Memory
1195959		sheina906	Colouring a rectangle (eJOI19_colouring)	C++20	0 / 100	2097 ms	25456 KiB

colouring

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define f first
#define s second


// int main()
// {
//     ll m, n; cin >> m >> n;
//     ll d = m+n-1;
//     ll mn = 100000000000000;
//     vector<ll> v1(d), v2(d);
//     for (ll &i : v1) cin >> i;
//     for (ll &i : v2) cin >> i;

//     for (ll k1 = 0; k1 < (1<<d); k1++)
//     {
//         ll k2 = 0, t = 0;
//         for (ll i = 0; i < m; i++) 
//         {
//             for (ll j = 0; j < n; j++) 
//             {
//                 if (!(k1 & (1<<(i-j+n-1)))) k2 |= (1<<(i+j));
//             }
//         }

//         for (int i = 0; i < d; i++) 
//         {
//             if (k1 & (1<<i)) t += v1[i];
//             if (k2 & (1<<i)) t += v2[i];
//         }

//         mn = min(mn, t);
//     }


//     cout << mn << '\n';


//     return 0;
// }



bool erase(bool r, int ind, vector<vector<ll>> &v, ll d, ll n, ll m)
{
    for (ll k = 0; k < d; k++) 
    {
        if (v[!r][k] != -1) continue;
        ll t = k+1+ind-n;
        if (t&1) continue;
        t /= 2;
        ll t1 = -t;
        t1 += r ? ind : k;
        if (0 <= t && t < m && 0 <= t1 && t1 < n) return false;
    }
    return true;
}

int main()
{
    ll m, n; cin >> m >> n;
    ll d = m+n-1, x = 0, t;
    vector<vector<ll>> v(2, vector<ll> (d));
    vector<pair<ll, pair<bool, ll>>> srt(2*d);
    for (int i = 0; i < d; i++) 
    {
        cin >> t;
        x += t;
        v[0][i] = t;
        srt[i] = {t, {0, i}};
    }
    for (int i = 0; i < d; i++)
    {
        cin >> t;
        x += t;
        v[1][i] = t;
        srt[i+d] = {t, {1, i}};
    }
    sort(srt.begin(), srt.end());


    for (int i = 2*d-1; i >= 0; i--)
    {
        if (erase(srt[i].s.f, srt[i].s.s, v, d, n, m))
        {
            x -= srt[i].f;
            v[srt[i].s.f][srt[i].s.s] = -1;
        }
    }


    cout << x << '\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