oj.uz

Submission #52857

# Submission time Handle Problem Language Result Execution time Memory
52857 2018-06-27T05:18:51 Z 윤교준(#1384) Popeala (CEOI16_popeala) C++11
0 / 100
 1286 ms 21156 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];

bitset<MAXT> B[MAXN];
int BS[MAXN][MAXT];

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

int N, T, K;

int main() {
	ios :: sync_with_stdio(false);

	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:30: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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2040 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 46 ms 4964 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1286 ms 21156 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 74.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 2040 KB Output isn't correct
2 Halted 0 ms 0 KB -