oj.uz

Submission #453795

# Submission time Handle Problem Language Result Execution time Memory
453795 2021-08-04T21:47:40 Z RGBB Mobitel (COCI19_mobitel) C++14
130 / 130
 2403 ms 3232 KB 
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
const int MAXR=300;
const int MAXS=1005;
const int mod=1e9+7;
int r,s,n,inp[MAXR][MAXR],dp1[MAXR][MAXS],dp2[MAXR][MAXS],cur1[MAXS],cur2[MAXS];//1 is range, 2 is value
int rp(int a,int b)
{
    return ceil((double)a/b);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>r>>s>>n;
    for(int i=0;i<r;i++)for(int y=0;y<s;y++)cin>>inp[i][y];
    int mr=floor(sqrt(n));//range from ceil(m/mr) to n
    int mv=rp(n,mr)-1;//range from 1 to ceil(m/mr)-1
    memset(dp1,0,sizeof(dp1));
    memset(dp2,0,sizeof(dp2));
    if(inp[0][0]<=mv)dp2[0][inp[0][0]]++;
    else dp1[0][rp(n,inp[0][0])]++;
    for(int i=0;i<r;i++)
    {
        for(int y=0;y<s;y++)
        {
            if(i==0&&y==0)continue;
            memset(cur1,0,sizeof(cur1));
            memset(cur2,0,sizeof(cur2));
            if(y!=0)
            {
                for(int j=1;j<=mv;j++)
                {
                    if(j*inp[i][y]<=mv)
                    {
                        cur2[j*inp[i][y]]+=dp2[y-1][j];
                        cur2[j*inp[i][y]]%=mod;
                    }
                    else
                    {
                        cur1[rp(rp(n,j),inp[i][y])]+=dp2[y-1][j];
                        cur1[rp(rp(n,j),inp[i][y])]%=mod;
                    }
                }
                for(int j=1;j<=mr;j++)
                {
                    cur1[rp(j,inp[i][y])]+=dp1[y-1][j];
                    cur1[rp(j,inp[i][y])]%=mod;
                }
            }
            for(int j=1;j<=mv;j++)
            {
                if(j*inp[i][y]<=mv)
                {
                    cur2[j*inp[i][y]]+=dp2[y][j];
                    cur2[j*inp[i][y]]%=mod;
                }
                else
                {
                    cur1[rp(rp(n,j),inp[i][y])]+=dp2[y][j];
                    cur1[rp(rp(n,j),inp[i][y])]%=mod;
                }
            }
            for(int j=1;j<=mr;j++)
            {
                cur1[rp(j,inp[i][y])]+=dp1[y][j];
                cur1[rp(j,inp[i][y])]%=mod;
            }
            for(int j=1;j<=mv;j++)dp2[y][j]=cur2[j];
            for(int j=1;j<=mr;j++)dp1[y][j]=cur1[j];
        }
    }
    cout<<dp1[s-1][1]<<"\n";
}

Subtask #1
130.0 / 130.0

# Verdict Execution time Memory Grader output
1 Correct 74 ms 3216 KB Output is correct
2 Correct 77 ms 3232 KB Output is correct
3 Correct 245 ms 2804 KB Output is correct
4 Correct 251 ms 2816 KB Output is correct
5 Correct 267 ms 2808 KB Output is correct
6 Correct 265 ms 2812 KB Output is correct
7 Correct 129 ms 2764 KB Output is correct
8 Correct 1290 ms 3140 KB Output is correct
9 Correct 2376 ms 3216 KB Output is correct
10 Correct 2403 ms 3216 KB Output is correct