oj.uz

Submission #125854

# Submission time Handle Problem Language Result Execution time Memory
125854 2019-07-06T13:08:47 Z tutis Popeala (CEOI16_popeala) C++17
26 / 100
 2000 ms 3704 KB 
/*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;
	{
		int kada[N];
		for (int i = 0; i < N; i++)
			kada[i] = 0;
		for (ll b = 1; b <= T; b++)
		{
			for (ll i = 0; i < N; i++)
			{
				if (res[i][b - 1] == '0')
				{
					kada[i] = b;
				}
			}
			int x[N];
			for (int i = 0; i < N; i++)
				x[i] = kada[i];
			sort(x, x + N, greater<int>());
			int i = 0;
			ll suma = 0;
			ll kiek = N;
			for (int a = b; a > 0; a--)
			{
				suma += p[a];
				while (i < N && x[i] >= a)
				{
					i++;
					kiek--;
				}
				for (ll c = 1; c <= S; c++)
					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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 632 KB Output is correct
2 Correct 19 ms 632 KB Output is correct
3 Correct 19 ms 632 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 370 ms 1400 KB Output is correct
2 Correct 691 ms 1968 KB Output is correct
3 Correct 1213 ms 2576 KB Output is correct

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 19 ms 632 KB Output is correct
4 Correct 19 ms 632 KB Output is correct
5 Correct 19 ms 632 KB Output is correct
6 Correct 370 ms 1400 KB Output is correct
7 Correct 691 ms 1968 KB Output is correct
8 Correct 1213 ms 2576 KB Output is correct
9 Execution timed out 2047 ms 3704 KB Time limit exceeded
10 Halted 0 ms 0 KB -