oj.uz

Submission #612609

# Submission time Handle Problem Language Result Execution time Memory
612609 2022-07-29T18:15:01 Z CSQ31 Popeala (CEOI16_popeala) C++17
100 / 100
 406 ms 14344 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e4+1;
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
typedef long long int ll;
int a[MAXN],n,m,s;
vector<int>pos[MAXN];
ll dp1[MAXN],dp2[MAXN],pre[51][MAXN];
void tran(){
	for(int j=0;j<=m;j++){
		for(int i=0;i<=n;i++){
			pre[j][i] = dp1[i] - a[i] * j;
			if(i)pre[j][i] = min(pre[j][i],pre[j][i-1]);
		}
	}
	for(int i=1;i<=n;i++){
		dp2[i] = pre[m][i-1] + m*a[i];
		int last = i-1;
		for(int j=m-1;j>=0;j--){
			last = min(pos[i][j]-1,last);
			if(last<0)break;
			dp2[i] = min(dp2[i],pre[j][last] + j*a[i]);
			
		}
	}
	/*
	for(int i=0;i<=n;i++)cout<<dp1[i]<<" ";
	cout<<'\n';
	for(int i=0;i<=n;i++)cout<<dp2[i]<<" ";
	cout<<'\n';
	* */
	cout<<dp2[n]<<'\n';
}
int main(){
	owo
	cin>>m>>n>>s;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		a[i]+=a[i-1];
		pos[i].resize(m);
	}
	for(int i=0;i<m;i++){
		int last = 0;
		for(int j=1;j<=n;j++){
			char c;
			cin>>c;
			if(c=='0')last = j;
			pos[j][i] = last;
		}
	}
	for(int i=1;i<=n;i++)sort(pos[i].begin(),pos[i].end());
	for(int i=0;i<=n;i++)dp1[i] = dp2[i] = 1e12;
	dp1[0] = 0;
	for(int i=1;i<=s;i++){
		tran();
		//cout<<dp2[n]<<" ";
		for(int j=0;j<=n;j++){
			dp1[j] = dp2[j];
			dp2[j] = 1e12;
		}
	}
	
	
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 928 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1360 KB Output is correct
2 Correct 9 ms 1332 KB Output is correct
3 Correct 10 ms 1364 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 2444 KB Output is correct
2 Correct 62 ms 3028 KB Output is correct
3 Correct 77 ms 3668 KB Output is correct

Subtask #4
74.0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 724 KB Output is correct
2 Correct 1 ms 928 KB Output is correct
3 Correct 10 ms 1360 KB Output is correct
4 Correct 9 ms 1332 KB Output is correct
5 Correct 10 ms 1364 KB Output is correct
6 Correct 44 ms 2444 KB Output is correct
7 Correct 62 ms 3028 KB Output is correct
8 Correct 77 ms 3668 KB Output is correct
9 Correct 121 ms 5400 KB Output is correct
10 Correct 156 ms 6748 KB Output is correct
11 Correct 365 ms 13908 KB Output is correct
12 Correct 372 ms 14344 KB Output is correct
13 Correct 406 ms 14284 KB Output is correct
14 Correct 394 ms 14288 KB Output is correct
15 Correct 381 ms 14268 KB Output is correct