oj.uz

Submission #116061

# Submission time Handle Problem Language Result Execution time Memory
116061 2019-06-10T09:57:24 Z tmwilliamlin168 Popeala (CEOI16_popeala) C++14
100 / 100
 911 ms 9848 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+2];
string r[mxN];
deque<int> dq[mxN+1];

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+2);
	}
	memset(dp, 0x3f, sizeof(dp));
	dp[0][0]=0;
	for(int i=1; i<=s; ++i) {
		for(int j=1; j<=t; ++j) {
			for(int k=0; k<=n; ++k) {
				for(int l=a[j-1][k+1]; l<a[j][k+1]; ++l) {
					while(dq[k].size()&&dp[i-1][dq[k].back()]-p[dq[k].back()]*k>dp[i-1][l]-p[l]*k)
						dq[k].pop_back();
					dq[k].push_back(l);
				}
				if(dq[k].size())
					dp[i][j]=min(dp[i-1][dq[k].front()]+(p[j]-p[dq[k].front()])*k, dp[i][j]);
			}
		}
		cout << dp[i][t] << "\n";
		for(int j=0; j<=n; ++j)
			dq[j].clear();
	}
}

Subtask #1
8.0 / 8.0

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

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 4480 KB Output is correct
2 Correct 25 ms 4556 KB Output is correct
3 Correct 26 ms 4480 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 102 ms 4992 KB Output is correct
2 Correct 152 ms 5216 KB Output is correct
3 Correct 178 ms 5624 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 6 ms 4324 KB Output is correct
3 Correct 27 ms 4480 KB Output is correct
4 Correct 25 ms 4556 KB Output is correct
5 Correct 26 ms 4480 KB Output is correct
6 Correct 102 ms 4992 KB Output is correct
7 Correct 152 ms 5216 KB Output is correct
8 Correct 178 ms 5624 KB Output is correct
9 Correct 249 ms 6144 KB Output is correct
10 Correct 400 ms 6776 KB Output is correct
11 Correct 770 ms 9720 KB Output is correct
12 Correct 781 ms 9720 KB Output is correct
13 Correct 901 ms 9820 KB Output is correct
14 Correct 911 ms 9848 KB Output is correct
15 Correct 886 ms 9820 KB Output is correct