oj.uz

Submission #52870

# Submission time Handle Problem Language Result Execution time Memory
52870 2018-06-27T05:41:09 Z 윤교준(#1384) Popeala (CEOI16_popeala) C++11
17 / 100
 2000 ms 23808 KB 
#include <bits/stdc++.h>
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;

const int MAXT = 4005;
const int MAXN = 55;
const int MAXK = 55;

int dp[MAXK][MAXT];

int C[MAXT][MAXT];

bool B[MAXN][MAXT];
int BS[MAXN][MAXT];

int S[MAXT];
int A[MAXT];

int N, T, K;

int main() {
	scanf("%d%d%d", &N, &T, &K);
	for(int i = 1; i <= T; i++) scanf("%d", &A[i]);
	for(int i = 1; i <= N; i++) {
		for(int j = 1; j <= T; j++) {
			char c; scanf(" %c", &c);
			B[i][j] = (bool)(c == '1');
		}
	}

	for(int i = 1; i <= T; i++)
		S[i] = S[i-1] + A[i];
	for(int i = 1; i <= N; i++) {
		for(int j = 1; j <= T; j++)
			BS[i][j] = BS[i][j-1] + (int)(!!B[i][j]);
		for(int s = 1; s <= T; s++) for(int e = s; e <= T; e++)
			if(BS[i][e] - BS[i][s-1] == e-s+1)
				C[s][e]++;
	}

	for(int j = 1; j <= K; j++) {
		for(int i = j; i <= T; i++) {
			int t = INF*2;
			for(int k = j-1; k < i; k++) {
				if(1 == j && k) continue;
				int r = dp[j-1][k] + (S[i] - S[k]) * C[k+1][i];
				if(r < t) t = r;
			}
			dp[j][i] = t;
		}
	}

	for(int i = 1; i <= K; i++)
		printf("%d\n", dp[i][T]);
	
	return 0;
}

Compilation message

popeala.cpp: In function 'int main()':
popeala.cpp:24:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d%d", &N, &T, &K);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
popeala.cpp:25:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i = 1; i <= T; i++) scanf("%d", &A[i]);
                              ~~~~~^~~~~~~~~~~~~
popeala.cpp:28:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    char c; scanf(" %c", &c);
            ~~~~~^~~~~~~~~~~

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 1000 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 3744 KB Output is correct
2 Correct 35 ms 3744 KB Output is correct
3 Correct 35 ms 3792 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1116 ms 13804 KB Output is correct
2 Execution timed out 2053 ms 23808 KB Time limit exceeded
3 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 1000 KB Output is correct
3 Correct 28 ms 3744 KB Output is correct
4 Correct 35 ms 3744 KB Output is correct
5 Correct 35 ms 3792 KB Output is correct
6 Correct 1116 ms 13804 KB Output is correct
7 Execution timed out 2053 ms 23808 KB Time limit exceeded
8 Halted 0 ms 0 KB -