Submission #160059

#	Time	Username	Problem	Language	Result	Execution time	Memory
160059		RedNextCentury	Mobitel (COCI19_mobitel)	C++14	52 / 130	213 ms	37752 KiB

mobitel

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll mod = 1000000007;
ll Power(ll a,ll b) {
    if (b==0)return 1;
    ll x = Power(a,b/2);
    x = (x*x)%mod;
    if (b%2)x=(x*a)%mod;
    return x;
}
const int problemsettersIQ = 404; // not found
pair<int,int>  dp[2][301][4001];
int len[2][301];
int a[problemsettersIQ][problemsettersIQ];
ll inv(ll x) {return Power(x,mod-2);}
int main()
{
    //ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int n,m,k;
    scanf("%d%d%d",&n,&m,&k);
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++) {
            scanf("%d",&a[i][j]);
        }
    }
    if (a[1][1]>k){
        printf("0\n");
        return 0;
    }
    dp[1][1][len[1][1]++]={a[1][1],1};
    for (int i=1;i<=n;i++) {
        for (int j=1;j<=m;j++) {
            if (i==1 && j==1)continue;
            if (i==1){
                for (int o=0;o<len[i%2][j-1];o++){
                    auto x = dp[i%2][j-1][o];
                    if (k/x.first < a[i][j])
                        break;
                    dp[i%2][j][len[i%2][j]++]={x.first*a[i][j],x.second};
                }
            }
            else if (j==1){

                for (int o=0;o<len[(i+1)%2][j];o++){
                    auto x = dp[(i+1)%2][j][o];
                    if (k/x.first < a[i][j])
                        break;
                    dp[i%2][j][len[i%2][j]++]={x.first*a[i][j],x.second};
                }
            }
            else {
                int l=0,r=0;
                while(l<len[(i+1)%2][j] && r<len[i%2][j-1]) {
                    if (dp[(i+1)%2][j][l].first==dp[i%2][j-1][r].first) {
                        if (k/dp[(i+1)%2][j][l].first < a[i][j])break;
                        dp[i%2][j][len[i%2][j]++]={dp[(i+1)%2][j][l].first*a[i][j],(dp[(i+1)%2][j][l].second+dp[i%2][j-1][r].second)%mod};
                        l++,r++;
                    } else if (dp[(i+1)%2][j][l].first<dp[i%2][j-1][r].first) {
                        if (k/dp[(i+1)%2][j][l].first < a[i][j])break;
                        dp[i%2][j][len[i%2][j]++]={dp[(i+1)%2][j][l].first*a[i][j],dp[(i+1)%2][j][l].second};
                        l++;
                    } else {
                        if (k/dp[i%2][j-1][r].first < a[i][j])break;
                        dp[i%2][j][len[i%2][j]++]={dp[i%2][j-1][r].first*a[i][j],dp[i%2][j-1][r].second};
                        r++;
                    }
                }
                while(l<len[(i+1)%2][j]) {
                    if (k/dp[(i+1)%2][j][l].first < a[i][j])break;
                    dp[i%2][j][len[i%2][j]++]={dp[(i+1)%2][j][l].first*a[i][j],dp[(i+1)%2][j][l].second};
                    l++;
                }
                while(r<len[i%2][j-1]) {
                    if (k/dp[i%2][j-1][r].first < a[i][j])break;
                    dp[i%2][j][len[i%2][j]++]={dp[i%2][j-1][r].first*a[i][j],dp[i%2][j-1][r].second};
                    r++;
                }
            }
        }
        for (int j=1;j<=m;j++) len[(i+1)%2][j]=0;
    }
    ll ret=1;

    for (int i=n+m-2 - (n-1) +1;i<=n+m-2;i++)ret=(ret*i)%mod;
    for (int i=1;i<=(n-1);i++)ret=(ret*inv(i))%mod;
    for (int o=0;o<len[n%2][m];o++) {
        auto x = dp[n%2][m][o];
        if (x.first>=k)break;
        ret-=x.second;
        ret+=mod;
        ret%=mod;
    }
    printf("%lld\n",ret);
}

Compilation message (stderr)

mobitel.cpp: In function 'int main()':
mobitel.cpp:21:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d%d",&n,&m,&k);
     ~~~~~^~~~~~~~~~~~~~~~~~~
mobitel.cpp:24:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
             scanf("%d",&a[i][j]);
             ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 52 / 130