Submission #159956

#	Time	Username	Problem	Language	Result	Execution time	Memory
159956		mdn2002	Mobitel (COCI19_mobitel)	C++14	26 / 130	505 ms	2916 KiB

mobitel

#include<bits/stdc++.h>
using namespace std;
int mod=1e9+7;
long long r,c,n,a[353][353],dp[353][353],dp1[353][353];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cin>>r>>c>>n;
    for(int i=0;i<r;i++)
    {
        for(int j=0;j<c;j++)
        {
            cin>>a[i][j];
        }
    }
    dp[0][min(a[0][0],n)]=1;
    for(int i=0;i<r;i++)
    {
        for(int j=0;j<c;j++)
        {
            if(i==0&&j==0)continue;
            for(int z=n;z>=0;z--)
            {
                long long x=z*a[i][j];
                if(dp1[j][z])dp[j][min(x,n)]+=dp1[j][z];
                if(dp[j-1][z]&&j!=0)dp[j][min(x,n)]+=dp[j-1][z];
                dp[j][min(x,n)]%=mod;
            }
        }
        for(int j=0;j<c;j++)
        {
            for(int z=0;z<=n;z++)
            {
                dp1[j][z]=dp[j][z];
                dp[j][z]=0;
            }
        }
    }
    cout<<dp1[c-1][n];
}

• Subtask 1: 26 / 130