oj.uz

Submission #116067

# Submission time Handle Problem Language Result Execution time Memory
116067 2019-06-10T10:15:33 Z tmwilliamlin168 Popeala (CEOI16_popeala) C++14
100 / 100
 293 ms 9720 KB 
#include <bits/stdc++.h>
using namespace std;

const int mxN=50, mxT=2e4, mxS=50;
int n, t, s, p[mxT+1], dp[mxS+1][mxT+1], a[mxT+1][mxN+1], b[mxN+1];
string r[mxN];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> t >> s;
	for(int i=0; i<t; ++i)
		cin >> p[i+1], p[i+1]+=p[i];
	for(int i=0; i<n; ++i)
		cin >> r[i];
	for(int i=0; i<t; ++i)
		for(int j=0; j<n; ++j)
			a[i+1][j]=r[j][i]&1?a[i][j]:i+1;
	for(int i=1; i<=t; ++i) {
		a[i][n]=i;
		sort(a[i], a[i]+n+1);
	}
	memset(dp, 0x3f, sizeof(dp));
	dp[0][0]=0;
	for(int i=1; i<=s; ++i) {
		memset(b, 0x3f, 4*n+4);
		for(int j=1; j<=t; ++j) {
			for(int k=0; k<=n; ++k) {
				for(int l=a[j-1][k]; l<a[j][k]; ++l)
					b[k]=min(dp[i-1][l]-p[l]*k, b[k]);
				dp[i][j]=min(b[k]+p[j]*k, dp[i][j]);
			}
		}
		cout << dp[i][t] << "\n";
	}
}

Subtask #1
8.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 4564 KB Output is correct
2 Correct 11 ms 4480 KB Output is correct
3 Correct 13 ms 4480 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 4956 KB Output is correct
2 Correct 54 ms 5120 KB Output is correct
3 Correct 60 ms 5496 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4352 KB Output is correct
2 Correct 5 ms 4352 KB Output is correct
3 Correct 13 ms 4564 KB Output is correct
4 Correct 11 ms 4480 KB Output is correct
5 Correct 13 ms 4480 KB Output is correct
6 Correct 41 ms 4956 KB Output is correct
7 Correct 54 ms 5120 KB Output is correct
8 Correct 60 ms 5496 KB Output is correct
9 Correct 76 ms 6144 KB Output is correct
10 Correct 122 ms 6612 KB Output is correct
11 Correct 194 ms 9648 KB Output is correct
12 Correct 215 ms 9592 KB Output is correct
13 Correct 265 ms 9720 KB Output is correct
14 Correct 293 ms 9720 KB Output is correct
15 Correct 257 ms 9720 KB Output is correct