oj.uz

Submission #160072

# Submission time Handle Problem Language Result Execution time Memory
160072 2019-10-25T21:31:30 Z RedNextCentury Mobitel (COCI19_mobitel) C++14
130 / 130
 4245 ms 10616 KB 
#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll mod = 1000000007;
vector<pair<int,int> > dp[2][303];
int a[303][303];
int main()
{
    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;
    printf("%lld\n",ret);
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Correct 159 ms 1016 KB Output is correct
2 Correct 106 ms 1016 KB Output is correct
3 Correct 117 ms 1272 KB Output is correct
4 Correct 122 ms 1400 KB Output is correct
5 Correct 378 ms 3704 KB Output is correct
6 Correct 335 ms 3588 KB Output is correct
7 Correct 124 ms 2296 KB Output is correct
8 Correct 2083 ms 7752 KB Output is correct
9 Correct 4142 ms 10616 KB Output is correct
10 Correct 4245 ms 10488 KB Output is correct