oj.uz

Submission #93914

# Submission time Handle Problem Language Result Execution time Memory
93914 2019-01-13T07:29:15 Z kjain_1810 Vođe (COCI17_vode) C++17
120 / 120
 2068 ms 197632 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 186 ms 196932 KB Output is correct
2 Correct 156 ms 196880 KB Output is correct
3 Correct 139 ms 196828 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 196832 KB Output is correct
2 Correct 134 ms 196856 KB Output is correct
3 Correct 136 ms 196984 KB Output is correct

Subtask #3
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 196856 KB Output is correct
2 Correct 137 ms 196840 KB Output is correct
3 Correct 135 ms 196884 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 196856 KB Output is correct
2 Correct 136 ms 196832 KB Output is correct
3 Correct 138 ms 196828 KB Output is correct

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 143 ms 196820 KB Output is correct
2 Correct 140 ms 197024 KB Output is correct
3 Correct 137 ms 196780 KB Output is correct

Subtask #6
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 196812 KB Output is correct
2 Correct 171 ms 196912 KB Output is correct
3 Correct 133 ms 196772 KB Output is correct

Subtask #7
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 292 ms 197064 KB Output is correct
2 Correct 358 ms 197156 KB Output is correct
3 Correct 1923 ms 197496 KB Output is correct

Subtask #8
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 630 ms 197212 KB Output is correct
2 Correct 1640 ms 197632 KB Output is correct
3 Correct 650 ms 197388 KB Output is correct

Subtask #9
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1854 ms 197592 KB Output is correct
2 Correct 149 ms 197112 KB Output is correct
3 Correct 141 ms 197112 KB Output is correct

Subtask #10
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2068 ms 197580 KB Output is correct
2 Correct 1781 ms 197368 KB Output is correct
3 Correct 1846 ms 197476 KB Output is correct