oj.uz

Submission #134099

# Submission time Handle Problem Language Result Execution time Memory
134099 2019-07-22T04:39:35 Z 이온조(#3229) Popeala (CEOI16_popeala) C++14
0 / 100
 111 ms 2652 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;
}

void dnc(int id, int s, int e, int l, int r) {
	if(e < s) return;
	int m = s+e >> 1;
	long long mn = INF; int mni = l;
	for(int i=l; i<=min(m-1, r); i++) {
		long long tmp = D[id-1][i] + C(i+1, m);
		if(mn > tmp) mn = tmp, mni = i;
	}
	D[id][m] = mn;
	dnc(id, s, m-1, l, mni);
	dnc(id, m+1, e, mni, r);
}

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++) {
		dnc(i, 0, T, 0, T-1);
		printf("%lld\n", D[i][T]);
	}
	return 0;
}

Compilation message

popeala.cpp: In function 'void dnc(int, int, int, int, int)':
popeala.cpp:16:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  int m = s+e >> 1;
          ~^~
popeala.cpp: In function 'int main()':
popeala.cpp:28: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:30:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&P[i]);
   ~~~~~^~~~~~~~~~~~
popeala.cpp:35: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
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 3 ms 632 KB Output isn't correct

Subtask #2
0 / 9.0

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

Subtask #3
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 111 ms 2652 KB Output isn't correct
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 Incorrect 3 ms 632 KB Output isn't correct