oj.uz

Submission #749508

# Submission time Handle Problem Language Result Execution time Memory
749508 2023-05-28T06:30:46 Z 박상훈(#9965) Popeala (CEOI16_popeala) C++17
8 / 100
 2000 ms 1240 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
constexpr int INF = 2e9 + 100;
int dp[55][20020], opt[55][20020], a[20020], aS[20020], n, t, s;
char b[55][20020], bS[22][20020];

int f(int l, int r){
	int ret = 0;
	for (int i=1;i<=n;i++){
		if (bS[i][r] - bS[i][l-1] == r-l+1) ret += aS[r] - aS[l-1];
	}
	return ret;
}

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

	cin >> n >> t >> s;
	for (int i=1;i<=t;i++){
		cin >> a[i];
		aS[i] = aS[i-1] + a[i];
	} 
	for (int i=1;i<=n;i++){
		cin >> (b[i]+1);
		for (int j=1;j<=t;j++){
			bS[i][j] = bS[i][j-1] + (b[i][j]=='1');
		}
	} 

	fill(dp[0]+1, dp[0]+t+1, INF);
	dp[0][0] = 0;
	
	for (int z=1;z<=s;z++){
		dp[z][0] = INF;
		for (int i=1;i<=t;i++){
			dp[z][i] = INF;
			for (int j=0;j<i;j++){
				int val = dp[z-1][j] + f(j+1, i);
				if (dp[z][i] > val){
					dp[z][i] = val;
					opt[z][i] = j;
				}
			}
		}

		printf("%d\n", dp[z][t]);
		// for (int i=1;i<=t;i++) printf("%d ", opt[z][i]);
		// printf("\n");
		// for (int i=1;i<t;i++) assert(opt[z][i] <= opt[z][i+1]);
	}
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 2 ms 596 KB Output is correct

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 451 ms 1196 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2057 ms 1240 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Incorrect 451 ms 1196 KB Output isn't correct
4 Halted 0 ms 0 KB -