oj.uz

Submission #52824

# Submission time Handle Problem Language Result Execution time Memory
52824 2018-06-27T03:11:18 Z tataky(#1371) Popeala (CEOI16_popeala) C++11
17 / 100
 351 ms 1116 KB 
#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;

int d[51][501];
int n, t[501], T, pt[501], s;
char ok[51][502];
int p[51][501];

int sc(int l, int r) {
	int sum = 0, ts = pt[r] - pt[l - 1];
	for (int i = 0; i < n; i++) {
		if (p[i][r] - p[i][l - 1] == r - l + 1) sum += ts;
	}
	return sum;
}

int f(int g, int k) {
	if (g == 0) return k == T + 1 ? 0 : 2000000001;
	if (k == T + 1) return g == 0 ? 0 : 2000000001;
	if (d[g][k] >= 0) return d[g][k];
	int res = 2000000001;
	for (int i = k; i <= T; i++) {
		int tt = f(g - 1, i + 1);
		if (tt > 2000000000) continue;
		res = min(res, tt + sc(k, i));
	}
	return d[g][k] = res;
}

int main() {
	scanf("%d %d %d", &n, &T, &s);
	for (int i = 1; i <= T; i++) {
		scanf("%d", &t[i]);
		pt[i] = pt[i - 1] + t[i];
	}
	for (int i = 0; i < n; i++) {
		scanf("%s", &ok[i][1]);
		for (int j = 1; j <= T; j++) {
			p[i][j] = p[i][j - 1] + (ok[i][j] - '0');
		}
	}
	memset(d, -1, sizeof(d));
	for (int i = 1; i <= s; i++) {
		printf("%d\n", f(i, 1));
	}
	return 0;
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &n, &T, &s);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
popeala.cpp:36:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &t[i]);
   ~~~~~^~~~~~~~~~~~~
popeala.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", &ok[i][1]);
   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 496 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 351 ms 804 KB Output is correct
2 Correct 338 ms 984 KB Output is correct
3 Correct 349 ms 984 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 19 ms 1116 KB Time limit exceeded (wall clock)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 496 KB Output is correct
3 Correct 351 ms 804 KB Output is correct
4 Correct 338 ms 984 KB Output is correct
5 Correct 349 ms 984 KB Output is correct
6 Execution timed out 19 ms 1116 KB Time limit exceeded (wall clock)
7 Halted 0 ms 0 KB -