Submission #106273

#	Time	Username	Problem	Language	Result	Execution time	Memory
106273		hamzqq9	Mobitel (COCI19_mobitel)	C++14	130 / 130	2333 ms	5672 KiB

mobitel

#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define pf push_front
#define ppb pop_back
#define ppf pop_front
#define umax(x,y) x=max(x,y)
#define umin(x,y) x=min(x,y)
#define ll long long 
#define ii pair<int,int>
#define iii pair<ii,int>
#define iiii pair<ii,ii>
#define sz(x) ((int) x.size())
#define orta ((bas+son)/2)
#define all(x) x.begin(),x.end()
#define pw(x) (1<<(x))
#define inf 100000009
#define MOD 1000000007
#define N 305
#define M 2500005
#define LOG 20
#define KOK 300
#define EPS 0.0000001
using namespace std;

int n,m,val;
int a[N][N];
int dp[2][N][1005][2];
int w[2][2]={1,0,0,1};

int add(int x,int y) {

	x+=y;

	if(x>=MOD) x-=MOD;
	if(x<0) x+=MOD;

	return x;

}

int main() {

	scanf("%d %d %d",&n,&m,&val);

	for(int i=1;i<=n;i++) {

		for(int j=1;j<=m;j++) {

			scanf("%d",&a[i][j]);

		}

	}

	if(a[1][1]<=1000) {

		dp[1][1][a[1][1]][0]=1;

	}
	else {

		dp[1][1][(val+a[1][1]-1)/a[1][1]][1]=1;

	}

	for(int i=1;i<=n;i++) {

		int cur=i&1;

		for(int j=1;j<=m;j++) {

			for(int way=0;way<2;way++) {

				int x=i+w[way][0];
				int y=j+w[way][1];

				if(x>n || y>m) continue ;

				int gval=a[x][y];

				for(int v=1;v<=1000;v++) {

					int nv=v*gval;

					if(nv<=1000) {

						dp[cur^(x!=i)][y][nv][0]=add(dp[cur^(x!=i)][y][nv][0],dp[cur][j][v][0]);

					}
					else {

						dp[cur^(x!=i)][y][(val+nv-1)/nv][1]=add(dp[cur^(x!=i)][y][(val+nv-1)/nv][1],dp[cur][j][v][0]);

					}

					dp[cur^(x!=i)][y][(v+gval-1)/gval][1]=add(dp[cur^(x!=i)][y][(v+gval-1)/gval][1],dp[cur][j][v][1]);

				}

			}

		}
		
		if(i!=n) {

			for(int j=1;j<=m;j++) {

				for(int v=1;v<=1000;v++) {

					for(int w=0;w<2;w++) {

						dp[cur][j][v][w]=0;

					}

				}

			}

		}

	}

	int ans=0;

	for(int v=1;v<=1000;v++) {

		if(v>=val) {

			ans=add(ans,dp[n&1][m][v][0]);

		}

	}

	ans=add(ans,dp[n&1][m][1][1]);

	printf("%d",ans);

}

Compilation message (stderr)

mobitel.cpp: In function 'int main()':
mobitel.cpp:45:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&n,&m,&val);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~
mobitel.cpp:51:9: 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