oj.uz

Submission #483792

# Submission time Handle Problem Language Result Execution time Memory
483792 2021-11-01T04:57:25 Z hollwo_pelw Popeala (CEOI16_popeala) C++17
0 / 100
 2000 ms 5068 KB 
#include <bits/stdc++.h>
using namespace std;

const int N = 55, T = 20005, S = 55;

int n, s, t, p[T], fail[T][N], dp[S][T], pre[N], curf[N];

inline void chkmin(int &a, int b) { a = a < b ? a : b; }

signed main() {
	cin.tie(0), cout.tie(0) -> sync_with_stdio(0);

	cin >> n >> t >> s;
	for (int i = 1; i <= t; i++)
		cin >> p[i], p[i] += p[i - 1];
	for (int i = 0; i < n; i++) {
		string r; cin >> r;
		for (int j = 0; j < t; j++)
			fail[j + 1][i] = r[j] == '0' ? j + 1 : fail[j][i];
	}
	for (int i = 1; i <= t; i++)
		sort(fail[i], fail[i] + n), fail[i][n] = i;
	memset(dp, 0x3f, sizeof dp);
	dp[0][0] = 0;
	// dp[i][j] = min dp[i - 1][k] + (p[j] - p[k]) * (\sum fail[j] >= k)
	// dp[i][j] = min x (min (dp[i - 1][k] - p[k] * x) + p[j] * x (k >= fail[j][x]))
	for (int i = 1; i <= s; i++) {
		memset(pre, 0x3f, sizeof pre);
		memset(curf,  0, sizeof curf);

		for (int j = 1; j <= t; j++) {
			for (int x = 0; x <= n; x++) {
				for (int &k = curf[x]; k < fail[j][x]; )
					chkmin(pre[x], dp[i - 1][k] - p[k] * x);
				chkmin(dp[i][j], pre[x] + p[j] * x);
			}
		}

		cout << dp[i][t] << '\n';
	}
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2069 ms 4556 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2070 ms 4684 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2070 ms 5068 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2069 ms 4556 KB Time limit exceeded
2 Halted 0 ms 0 KB -