oj.uz

Submission #134104

# Submission time Handle Problem Language Result Execution time Memory
134104 2019-07-22T04:46:28 Z 이온조(#3229) Popeala (CEOI16_popeala) C++14
17 / 100
 2000 ms 129008 KB 
#include <bits/stdc++.h>
using namespace std;

const long long INF = 1LL * 1e18;
int N, T, S, P[20009], R[55][20009], F[55][20009], PS[20009];
long long D[55][20009], M[4009][4009];

int C(int s, int e) {
	if(M[s][e] != -1) return M[s][e];
	int ret = 0;
	for(int i=1; i<=N; i++) if(F[i][e] - F[i][s-1] == e-s+1) ret += PS[e] - PS[s-1];
	return M[s][e] = ret;
}

int main() {
	scanf("%d%d%d",&N,&T,&S);
	for(int i=1; i<=T; i++) {
		scanf("%d",&P[i]);
		PS[i] = PS[i-1] + P[i];
	}
	for(int i=1; i<=N; i++) {
		for(int j=1; j<=T; j++) {
			scanf("%1d",&R[i][j]);
			F[i][j] = F[i][j-1] + R[i][j];
		}
	}
	memset(M, -1, sizeof(M));
	for(int i=1; i<=T; i++) D[0][i] = INF;
	for(int i=1; i<=S; i++) {
		for(int j=0; j<=T; j++) {
			D[i][j] = INF;
			for(int k=0; k<j; k++) {
				D[i][j] = min(D[i][j], D[i-1][k] + C(k+1, j));
			}
		}
		printf("%lld\n", D[i][T]);
	}
	return 0;
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:16: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:18:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&P[i]);
   ~~~~~^~~~~~~~~~~~
popeala.cpp:23:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%1d",&R[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 126200 KB Output is correct
2 Correct 109 ms 126584 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 127096 KB Output is correct
2 Correct 144 ms 127160 KB Output is correct
3 Correct 143 ms 127096 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1466 ms 128632 KB Output is correct
2 Execution timed out 2061 ms 129008 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 108 ms 126200 KB Output is correct
2 Correct 109 ms 126584 KB Output is correct
3 Correct 143 ms 127096 KB Output is correct
4 Correct 144 ms 127160 KB Output is correct
5 Correct 143 ms 127096 KB Output is correct
6 Correct 1466 ms 128632 KB Output is correct
7 Execution timed out 2061 ms 129008 KB Time limit exceeded
8 Halted 0 ms 0 KB -