oj.uz

Submission #116057

# Submission time Handle Problem Language Result Execution time Memory
116057 2019-06-10T09:51:05 Z tmwilliamlin168 Popeala (CEOI16_popeala) C++14
100 / 100
 983 ms 11000 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);
				}
				while(dq[k].size()&&dq[k].front()<a[j][k])
					dq[k].pop_front();
				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 5 ms 4352 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 4480 KB Output is correct
2 Correct 29 ms 4564 KB Output is correct
3 Correct 29 ms 4608 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 4992 KB Output is correct
2 Correct 170 ms 5324 KB Output is correct
3 Correct 205 ms 5752 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 30 ms 4480 KB Output is correct
4 Correct 29 ms 4564 KB Output is correct
5 Correct 29 ms 4608 KB Output is correct
6 Correct 116 ms 4992 KB Output is correct
7 Correct 170 ms 5324 KB Output is correct
8 Correct 205 ms 5752 KB Output is correct
9 Correct 283 ms 6548 KB Output is correct
10 Correct 439 ms 7316 KB Output is correct
11 Correct 867 ms 10872 KB Output is correct
12 Correct 877 ms 11000 KB Output is correct
13 Correct 970 ms 10872 KB Output is correct
14 Correct 983 ms 10872 KB Output is correct
15 Correct 961 ms 10872 KB Output is correct