Submission #1317996

#	Time	Username	Problem	Language	Result	Execution time	Memory
1317996		foxserg	Mosaic (IOI24_mosaic)	C++20	22 / 100	1202 ms	2162688 KiB

mosaic

#include <bits/stdc++.h>
#include "mosaic.h"

using namespace std;

using ll = long long;

vector <ll> mosaic(vector <int> X, vector <int> Y,
    vector <int> T, vector <int> B, vector <int> L, vector <int> R) {
    
    int n = X.size();
    int q = T.size();

    int A[n][n];
    for (int i = 0; i < n; ++i) {
        A[0][i] = X[i];
    }
    for (int i = 0; i < n; ++i) {
        A[i][0] = Y[i];
    }

    for (int i = 1; i < n; ++i) {
        for (int j = 1; j < n; ++j) {
            if (A[i - 1][j] || A[i][j - 1]) {
                A[i][j] = 0;
            } else {
                A[i][j] = 1;
            }
        }
    }

    int pref[n + 1][n + 1];
    for (int i = 0; i <= n; ++i) {
        pref[0][i] = 0;
        pref[i][0] = 0;
    }

    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            pref[i][j] = pref[i - 1][j] + pref[i][j - 1] - pref[i - 1][j - 1] + A[i - 1][j - 1];
        }
    }

    vector <ll> C(q);
    for (int i = 0; i < q; ++i) {
        C[i] = pref[B[i] + 1][R[i] + 1];
        C[i] -= pref[B[i] + 1][L[i]];
        C[i] -= pref[T[i]][R[i] + 1];
        C[i] += pref[T[i]][L[i]];
    }

    return C;
}

• Subtask 0: 0 / 0
• Subtask 1: 5 / 5
• Subtask 2: 7 / 7
• Subtask 3: 0 / 7
• Subtask 4: 10 / 10
• Subtask 5: 0 / 8
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19
• Subtask 8: 0 / 22