Submission #125846

#	Time	Username	Problem	Language	Result	Execution time	Memory
125846		tutis	Popeala (CEOI16_popeala)	C++17	17 / 100	2066 ms	1528 KiB

popeala

/*input
2 3 3
4 3 5
101
110
*/
#pragma GCC optimize ("O3")
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const ll modulo = 1000000007;
int main()
{
	ll N, T, S;
	cin >> N >> T >> S;
	ll p[T + 1];
	for (ll i = 1; i <= T; i++)
		cin >> p[i];
	string res[N];
	for (ll i = 0; i < N; i++)
		cin >> res[i];
	ll dp[S + 1][T + 1];
	for (ll a = 0; a <= S; a++)
	{
		for (ll b = 0; b <= T; b++)
		{
			dp[a][b] = 1e15;
		}
	}
	dp[0][0] = 0;
	for (ll c = 1; c <= S; c++)
	{
		for (ll b = 1; b <= T; b++)
		{
			vector<bool>ok(N, true);
			ll kiek = N;
			ll suma = 0;
			for (ll a = b; a > 0; a--)
			{
				suma += p[a];
				for (ll i = 0; i < N; i++)
				{
					if (res[i][a - 1] == '0')
					{
						if (ok[i])
						{
							ok[i] = false;
							kiek--;
						}
					}
				}
				dp[c][b] = min(dp[c][b], dp[c - 1][a - 1] + kiek * suma);
			}
		}
	}
	for (ll c = 1; c <= S; c++)
	{
		cout << dp[c][T] << "\n";
	}
}

• Subtask 1: 8 / 8
• Subtask 2: 9 / 9
• Subtask 3: 0 / 9
• Subtask 4: 0 / 74