Submission #1309547

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309547		zadniprovska	Colouring a rectangle (eJOI19_colouring)	C++20	0 / 100	2 ms	572 KiB

colouring

#include <bits/stdc++.h>
 
using namespace std;
 
#define ll long long
#define ld long double
#define ull unsigned long long
#define pll pair<ll, ll>
#define ppll pair< pair<long long, long long>, long long >
#define ff first
#define ss second
#define pb push_back
#define pf push_front
 
const ll DIM = 500 + 7;
const ll INF = 1e9;
const ll mod = 998244353;
const ll maxlog = 20;
const ll bsize = 350;

ll a[DIM], b[DIM];
ll p[DIM][DIM];

void solve() {

    ll n, m;
    cin >> n >> m;

    for (int i=1; i<=n+m-1; i++) {
        cin >> a[i];
    }
    for (int i=1; i<=n+m-1; i++) {
        cin >> b[i];
    }

    ll mn = INF;
    for (int mask=1; mask<(1 << (2*n + 2*m - 2)); mask++) {

        for (int i=1; i<=n; i++) {
            for (int j=1; j<=m; j++) {
                p[i][j] = 0;
            }
        }
        ll cost = 0;

        ll i = 1, j = m;
        for (int bit=0; bit<(n + m - 1); bit++) {

            if (mask & (1 << bit)) {
                cost += a[bit+1];
                if (cost > mn) break;

                ll ci = i, cj = j;
                while (ci <= n && cj <= m) {
                    p[ci][cj] = 1;
                    ci++; cj++;
                }
            }

            if (j == 1) i++;
            else j--;

        }

        if (cost > mn) continue;

        i = 1; j = 1;
        for (int bit=n+m-1; bit<(2*n + 2*m - 2); bit++) {

            if (mask & (1 << bit)) {
                cost += b[bit-(n+m-1)+1];
                if (cost > mn) break;

                ll ci = i, cj = j;
                while (ci <= n && cj >= 1) {
                    p[ci][cj] = 1;
                    ci++; cj--;
                }
            }

            if (j == m) i++;
            else j++;

        }
        

        ll ok = 1;
        for (int i=1; i<=n; i++) {
            for (int j=1; j<=m; j++) {
                if (!p[i][j]) {
                    ok = 0;
                    break;
                }
            } 
            if (!ok) break;
        }

        if (ok) mn = min(mn, cost);
    }

    cout << mn << endl;



}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    //freopen("atlarge.in", "r", stdin);
    //freopen("atlarge.out", "w", stdout);
 
    int ntest = 1;
    //cin >> ntest;
    while (ntest--) {
        solve();
    }
    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