Cod sursa(job #1453009)

Utilizator GeiGeiGeorge Cioroiu GeiGei Data 22 iunie 2015 16:31:12
Problema Patrate2 Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <cstdio>
#include <iostream>

using namespace std;

int main() {
    freopen("luna.in", "r", stdin);
    freopen("luna.out", "w", stdout);

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> m >> n;
    int a[55][55], s[55][55], dp[5005][105];
    bool al[5005];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a[i][j];
            al[a[i][j]] = true;
        }
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (s[i][j] == 0) {
                for (int k = i; k < m && a[i][j] == a[k][j]; k++) {
                    s[k][j] = k - i + 1;
                }
            }
        }
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            int k = j, lun = 1, lat = s[i][j], nr = a[i][j];
            if (lun > dp[nr][lat]) {
                dp[nr][lat] = lun;
                dp[nr][lun] = lat;
            }
            k++;
            while (k < n && a[i][k] == nr) {
                lun++;
                lat = (lat < s[i][k]) ? lat : s[i][k];
                if (lun > dp[nr][lat]) {
                    dp[nr][lat] = lun;
                    dp[nr][lun] = lat;
                }
                k++;
            }
        }
    }
    int k;
    cin >> k;
    for (int i = 0; i < k; i++) {
        int x, b, c;
        cin >> x >> b >> c;
        if (!al[x]) {
            cout << "Tara de provenienta nu are parcele pe Luna!\n";
            continue;
        }
        if (dp[x][b] < c) {
            cout << "Cererea nu poate fi satisfacuta!\n";
            continue;
        }
        cout << "Cererea poate fi satisfacuta!\n";
    }
    return 0;
}