oj.uz

Submission #49643

# Submission time Handle Problem Language Result Execution time Memory
49643 2018-06-01T14:14:12 Z IvanC Vođe (COCI17_vode) C++17
120 / 120
 2305 ms 198220 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5010;

int N,M,K;
int dp[MAXN][MAXN],somatorio[MAXN][MAXN],proximo[MAXN],vetor[MAXN];

int calcula(int pos,int numero);

int solve(int pos,int numero){
	if(dp[pos][numero] != -1) return dp[pos][numero];
	if(numero == M - 1) return dp[pos][numero] = 0;
	int nxt = proximo[pos];
	int lo = numero + 1;
	int hi = min(numero + K,M);
	int tam = hi - lo + 1;
	int valor = calcula(nxt,lo) - calcula(nxt,hi+1);
	if(vetor[pos] == vetor[nxt]){
		if(valor > 0) return dp[pos][numero] = 1;
		else return dp[pos][numero] = 0;
	}
	else{
		if(valor != tam) return dp[pos][numero] = 1;
		else return dp[pos][numero] = 0;
	}
}

int calcula(int pos,int numero){
	if(numero >= M) return 0;
	if(somatorio[pos][numero] != -1) return somatorio[pos][numero];
	return somatorio[pos][numero] = calcula(pos,numero+1) + solve(pos,numero);
}

int main(){
	memset(dp,-1,sizeof(dp));
	memset(somatorio,-1,sizeof(somatorio));
	scanf("%d %d %d",&N,&M,&K);
	for(int i = 1;i<=N;i++){
		scanf("%d",&vetor[i]);
		proximo[i] = i+1;
	}
	proximo[N] = 1;
	for(int i = 1;i<=N;i++){
		printf("%d ",vetor[i]^1^solve(i,0));
	}
	printf("\n");
	return 0;
}

Compilation message

vode.cpp: In function 'int main()':
vode.cpp:38:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&N,&M,&K);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
vode.cpp:40:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&vetor[i]);
   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 196824 KB Output is correct
2 Correct 162 ms 196852 KB Output is correct
3 Correct 149 ms 196980 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 164 ms 196980 KB Output is correct
2 Correct 151 ms 197024 KB Output is correct
3 Correct 156 ms 197140 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 155 ms 197188 KB Output is correct
2 Correct 149 ms 197188 KB Output is correct
3 Correct 160 ms 197204 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 162 ms 197204 KB Output is correct
2 Correct 177 ms 197256 KB Output is correct
3 Correct 160 ms 197256 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 192 ms 197256 KB Output is correct
2 Correct 179 ms 197256 KB Output is correct
3 Correct 166 ms 197256 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 163 ms 197256 KB Output is correct
2 Correct 164 ms 197256 KB Output is correct
3 Correct 166 ms 197312 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 385 ms 197512 KB Output is correct
2 Correct 406 ms 197512 KB Output is correct
3 Correct 2081 ms 198088 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 693 ms 198088 KB Output is correct
2 Correct 1794 ms 198132 KB Output is correct
3 Correct 648 ms 198132 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2157 ms 198132 KB Output is correct
2 Correct 156 ms 198132 KB Output is correct
3 Correct 150 ms 198132 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2305 ms 198220 KB Output is correct
2 Correct 1779 ms 198220 KB Output is correct
3 Correct 1856 ms 198220 KB Output is correct