Submission #100299

#	Time	Username	Problem	Language	Result	Execution time	Memory
100299		Shtef	Mobitel (COCI19_mobitel)	C++14	26 / 130	201 ms	3712 KiB

mobitel

#include <iostream>

using namespace std;

typedef long long ll;

ll n, m, k, a[305][305], dp[2][305][305];
const ll mod = (ll)1e9 + 7;

int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> k;
for(int i = 1 ; i <= n ; ++i){
	for(int j = 1 ; j <= m ; ++j){
		cin >> a[i][j];
	}
}
dp[0][1][1] = 1;
for(int i = 1 ; i <= n ; ++i){
	for(int j = 1 ; j <= m ; ++j){
		for(int v = 1 ; v <= k ; ++v){
			dp[i & 1][j][v] = 0;
		}
	}
	for(int j = 1 ; j <= m ; ++j){
		for(int v = k ; v >= 1 ; --v){
			dp[i & 1][j][min(v * a[i][j], k)] = (dp[i & 1][j][min(v * a[i][j], k)] + dp[(i & 1) ^ 1][j][v]) % mod;
			dp[i & 1][j][min(v * a[i][j], k)] = (dp[i & 1][j][min(v * a[i][j], k)] + dp[i & 1][j - 1][v]) % mod;
		}
	}
}
cout << dp[n & 1][m][k] << endl;

return 0;
}

• Subtask 1: 26 / 130