oj.uz

Submission #116066

# Submission time Handle Problem Language Result Execution time Memory
116066 2019-06-10T10:14:14 Z tmwilliamlin168 Popeala (CEOI16_popeala) C++14
100 / 100
 293 ms 9976 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]);
				if(a[j][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 4480 KB Output is correct
2 Correct 12 ms 4480 KB Output is correct
3 Correct 13 ms 4608 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 4992 KB Output is correct
2 Correct 56 ms 5368 KB Output is correct
3 Correct 63 ms 5504 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 4480 KB Output is correct
4 Correct 12 ms 4480 KB Output is correct
5 Correct 13 ms 4608 KB Output is correct
6 Correct 44 ms 4992 KB Output is correct
7 Correct 56 ms 5368 KB Output is correct
8 Correct 63 ms 5504 KB Output is correct
9 Correct 81 ms 6272 KB Output is correct
10 Correct 129 ms 6724 KB Output is correct
11 Correct 218 ms 9848 KB Output is correct
12 Correct 236 ms 9848 KB Output is correct
13 Correct 293 ms 9728 KB Output is correct
14 Correct 289 ms 9864 KB Output is correct
15 Correct 289 ms 9976 KB Output is correct