oj.uz

Submission #52867

# Submission time Handle Problem Language Result Execution time Memory
52867 2018-06-27T05:35:41 Z 윤교준(#1384) Popeala (CEOI16_popeala) C++11
17 / 100
 2000 ms 24768 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;

ll 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() {
	cin >> N >> T >> K;
	for(int i = 1; i <= T; i++) cin >> 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 i = 0; i < MAXK; i++)
		fill(dp[i], dp[i]+MAXT, INFLL);
	dp[0][0] = 0;

	for(int j = 1; j <= K; j++) {
		for(int i = j; i <= T; i++) {
			ll t = INFLL;
			for(int k = j-1; k < i; k++) {
				ll r = dp[j-1][k] + ll(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("%lld\n", dp[i][T]);
	
	return 0;
}

Compilation message

popeala.cpp: In function 'int main()':
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 3 ms 2040 KB Output is correct
2 Correct 4 ms 2664 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 5152 KB Output is correct
2 Correct 42 ms 5216 KB Output is correct
3 Correct 38 ms 5216 KB Output is correct

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1054 ms 14852 KB Output is correct
2 Execution timed out 2055 ms 24768 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2040 KB Output is correct
2 Correct 4 ms 2664 KB Output is correct
3 Correct 30 ms 5152 KB Output is correct
4 Correct 42 ms 5216 KB Output is correct
5 Correct 38 ms 5216 KB Output is correct
6 Correct 1054 ms 14852 KB Output is correct
7 Execution timed out 2055 ms 24768 KB Time limit exceeded
8 Halted 0 ms 0 KB -