oj.uz

Submission #134098

# Submission time Handle Problem Language Result Execution time Memory
134098 2019-07-22T04:33:56 Z 이온조(#3229) Popeala (CEOI16_popeala) C++14
17 / 100
 2000 ms 2236 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];

int C(int s, int 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 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];
		}
	}
	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:15: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:17:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&P[i]);
   ~~~~~^~~~~~~~~~~~
popeala.cpp:22: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 2 ms 376 KB Output is correct
2 Correct 4 ms 760 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 523 ms 1372 KB Output is correct
2 Correct 523 ms 1564 KB Output is correct
3 Correct 506 ms 1484 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2041 ms 2236 KB Time limit exceeded
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 4 ms 760 KB Output is correct
3 Correct 523 ms 1372 KB Output is correct
4 Correct 523 ms 1564 KB Output is correct
5 Correct 506 ms 1484 KB Output is correct
6 Execution timed out 2041 ms 2236 KB Time limit exceeded
7 Halted 0 ms 0 KB -