oj.uz

답안 #134178

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
134178 2019-07-22T07:58:14 Z 이온조(#3229) 조교 (CEOI16_popeala) C++14
17 / 100
 553 ms 2828 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=i-1; k<=2*i && k<j; k++) {
				D[i][j] = min(D[i][j], D[i-1][k] + C(k+1, j));
			}
			for(int k=max(j-i, 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 128 ms 1384 KB Output is correct
2 Correct 116 ms 1324 KB Output is correct
3 Correct 123 ms 1432 KB Output is correct

Subtask #3
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 553 ms 2828 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 760 KB Output is correct
3 Correct 128 ms 1384 KB Output is correct
4 Correct 116 ms 1324 KB Output is correct
5 Correct 123 ms 1432 KB Output is correct
6 Incorrect 553 ms 2828 KB Output isn't correct
7 Halted 0 ms 0 KB -