Submission #160069

#	Time	Username	Problem	Language	Result	Execution time	Memory
160069		RedNextCentury	Mobitel (COCI19_mobitel)	C++14	104 / 130	5926 ms	65536 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
vector<pair<int,int> > dp[2][problemsettersIQ];
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].emplace_back(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 (auto x:dp[i%2][j-1]){
                    if (k/x.first < a[i][j])
                        break;
                    dp[i%2][j].emplace_back(x.first*a[i][j],x.second);
                }
            }
            else if (j==1){

                for (auto x:dp[(i+1)%2][j]){
                    if (k/x.first < a[i][j])
                        break;
                    dp[i%2][j].emplace_back(x.first*a[i][j],x.second);
                }
            }
            else {
                int l=0,r=0;
                vector<pair<int,int> >& L = dp[(i+1)%2][j];
                vector<pair<int,int> >& R = dp[i%2][j-1];
                while(l<L.size() && r<R.size()) {
                    if (L[l].first==R[r].first) {
                        if (k/L[l].first < a[i][j])break;
                        dp[i%2][j].emplace_back(L[l].first*a[i][j],(L[l].second+R[r].second)%mod);
                        l++,r++;
                    } else if (L[l].first<R[r].first) {
                        if (k/L[l].first < a[i][j])break;
                        dp[i%2][j].emplace_back(L[l].first*a[i][j],L[l].second);
                        l++;
                    } else {
                        if (k/R[r].first < a[i][j])break;
                        dp[i%2][j].emplace_back(R[r].first*a[i][j],R[r].second);
                        r++;
                    }
                }
                while(l<L.size()) {
                    if (k/L[l].first < a[i][j])break;
                    dp[i%2][j].emplace_back(L[l].first*a[i][j],L[l].second);
                    l++;
                }
                while(r<R.size()) {
                    if (k/R[r].first < a[i][j])break;
                    dp[i%2][j].emplace_back(R[r].first*a[i][j],R[r].second);
                    r++;
                }
            }
            if (dp[i%2][j].size()>=3000 && (n>=100 || m>=100)) {
                vector<pair<int, int> > tmp;
                for (auto x:dp[i % 2][j]) {
                    if (tmp.empty())tmp.push_back(x);
                    else if (k / tmp.back().first == k / x.first) {
                        tmp[tmp.size() - 1].second = (tmp[tmp.size() - 1].second + x.second) % mod;
                    } else {
                        tmp.push_back(x);
                    }
                }
                dp[i % 2][j] = tmp;
            }
        }
        for (int j=1;j<=m;j++) dp[(i+1)%2][j].clear();
    }
    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 (auto x:dp[n%2][m]) {
        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:53:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 while(l<L.size() && r<R.size()) {
                       ~^~~~~~~~~
mobitel.cpp:53:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 while(l<L.size() && r<R.size()) {
                                     ~^~~~~~~~~
mobitel.cpp:68:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 while(l<L.size()) {
                       ~^~~~~~~~~
mobitel.cpp:73:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 while(r<R.size()) {
                       ~^~~~~~~~~
mobitel.cpp:20: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:23: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: 104 / 130