제출 #1339965

#제출 시각아이디문제언어결과실행 시간메모리
1339965darius1414Mobitel (COCI19_mobitel)C++20
104 / 130
560 ms9472 KiB
#include <bits/stdc++.h>
#define nmx 305
#define mod 1000000007
using namespace std;

int n, m, k, v[nmx][nmx], r[2005], dp[2][nmx][2005], ct, from[1000005];
bitset <1000005> vf;

int main()
{
    // Optimizare pentru citire/scriere rapidă
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> n >> m >> k)) return 0;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> v[i][j];

    // 1. Generarea stărilor unice necesare (discretizare)
    int sq = int(sqrt(k));
    for (int i = 1; i <= sq; i++)
    {
        if (i == sq && i * i == k)
        {
            int x2 = k / i;
            if (x2 * i < k)
                x2++;
            if (!vf[x2])
            {
                r[++ct] = x2;
                vf[x2] = 1;
            }
            continue;
        }
        int x2 = k / i;
        if (x2 * i < k)
            x2++;
        if (!vf[x2])
        {
            r[++ct] = x2;
            vf[x2] = 1;
        }
        if (!vf[i])
        {
            r[++ct] = i;
            vf[i] = 1;
        }
    }

    sort(r + 1, r + ct + 1);

    // 2. Construirea vectorului 'from' pentru maparea produselor
    int st = 1;
    for (int i = 1; i <= k; i++)
    {
        if (r[st] == i)
        {
            from[i] = st;
            st++;
        }
        else
        {
            from[i] = from[i - 1];
        }
    }

    // 3. Setarea cazului de bază logic
    dp[(n + 1) % 2][m][ct] = 1;

    // 4. Parcurgerea DP inversă (Sliding Window pe linii)
    for (int i = n; i >= 1; i--)
    {
        for (int j = m; j >= 1; j--)
        {
            for (int l = 1; l <= ct; l++)
            {
                long long prod = 1LL * r[l] * v[i][j];
                int fromwh = from[min(1LL * k, prod)];

                // FIX: 1LL aplicat primului termen pentru a preveni orice Integer Overflow în timpul adunării
                dp[i % 2][j][l] = (1LL * dp[1 - i % 2][j][fromwh] + dp[i % 2][j + 1][fromwh]) % mod;
            }
        }
    }

    // Deoarece bucla pentru i se termină mereu la 1, răspunsul va fi mereu pe linia 1 % 2 = 1.
    cout << dp[1][1][1] << "\n";

    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...