Cod sursa(job #2760244)

Utilizator StefanSanStanescu Stefan StefanSan Data 24 iunie 2021 12:25:08
Problema Diamant Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.68 kb
#include      <iostream>
#include      <fstream>
#include      <algorithm>

using namespace std;

ifstream in("diamant.in");
ofstream out("diamant.out");

int n, m, x, dp[401][100006], val[401], p;

int main() {
	ios_base::sync_with_stdio(false);
	in.tie(NULL), out.tie(NULL);

	in >> n >> m >> x;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			val[++p] = i * j;
		}
	}

	for (int i = 1; i <= p; i++) {
		for (int w = 1; w <= x; w++) {
			if (i == 1 || w == 1) dp[i][w] = 0;
			else if (val[i - 1] <= w)
				dp[i][w] = max(1 + dp[i - 1][w - val[i - 1]], dp[i - 1][w]);
			else dp[i][w] = dp[i - 1][w];
		}
	}

	out << dp[p][x];

	return 0;
}