제출 #453795

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
453795		RGBB	Mobitel (COCI19_mobitel)	C++14	130 / 130	2403 ms	3232 KiB

mobitel

#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 / 130