Submission #160071

#	Time	Username	Problem	Language	Result	Execution time	Memory
160071		RedNextCentury	Mobitel (COCI19_mobitel)	C++14	130 / 130	4218 ms	10744 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);
    k--;
    for (int i=1;i<=n;i++){
        for (int j=1;j<=m;j++) {
            scanf("%d",&a[i][j]);
        }
    }
    dp[1][1].emplace_back(k/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]){
                    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]){
                    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) {
                        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) {
                        dp[i%2][j].emplace_back(L[l].first/a[i][j],L[l].second);
                        l++;
                    } else {
                        dp[i%2][j].emplace_back(R[r].first/a[i][j],R[r].second);
                        r++;
                    }
                }
                while(l<L.size()) {
                    dp[i%2][j].emplace_back(L[l].first/a[i][j],L[l].second);
                    l++;
                }
                while(r<R.size()) {
                    dp[i%2][j].emplace_back(R[r].first/a[i][j],R[r].second);
                    r++;
                }
            }
            vector<pair<int, int> > tmp;
            for (auto x:dp[i % 2][j]) {
                if (tmp.empty())tmp.push_back(x);
                else if (tmp.back().first ==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=0;
    for (auto x:dp[n%2][m]) {
        if (x.first==0) {
            ret+=x.second;
            ret%=mod;
            //ret+=mod;
            //ret%=mod;
        }
    }
    printf("%lld\n",ret);
}

Compilation message (stderr)

mobitel.cpp: In function 'int main()':
mobitel.cpp:46:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 while(l<L.size() && r<R.size()) {
                       ~^~~~~~~~~
mobitel.cpp:46:38: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 while(l<L.size() && r<R.size()) {
                                     ~^~~~~~~~~
mobitel.cpp:58:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 while(l<L.size()) {
                       ~^~~~~~~~~
mobitel.cpp:62: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: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: 130 / 130