oj.uz

Submission #40289

# Submission time Handle Problem Language Result Execution time Memory
40289 2018-01-30T23:58:26 Z IvanC Difference (POI11_roz) C++14
100 / 100
 255 ms 17260 KB 
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+10;
const int ALPHABET_SIZE = 26;
vector<int> aparece[ALPHABET_SIZE];
int vetor[MAXN],soma[MAXN],N,resposta;
int calc(int a,int b){return soma[b] - soma[a-1];}
int main(){
	scanf("%d",&N);
	for(int i = 1;i<=N;i++){
		char c;
		scanf(" %c",&c);
		vetor[i] = c - 'a';
		aparece[vetor[i]].push_back(i);
	}
	for(int letra = 0;letra<ALPHABET_SIZE;letra++){
		for(int i = 1;i<=N;i++){
			soma[i] = soma[i-1] + (vetor[i] == letra);
		}
		soma[N+1] = soma[N];
		for(int outra = 0;outra < ALPHABET_SIZE;outra++){
			if(outra == letra) continue;
			int minimo = 0;
			for(int i = 0;i<aparece[outra].size();i++){
				int proxima = 0;
				if(i + 1 == aparece[outra].size()) proxima = N;
				else proxima = aparece[outra][i+1] - 1;
				int j = i + 1;
				resposta = max(resposta, calc(1,proxima) - j - minimo );
				minimo = min(minimo, -j + calc(1,aparece[outra][i]) );
			}
		}
	}
	printf("%d\n",resposta);
	return 0;
}

Compilation message

roz.cpp: In function 'int main()':
roz.cpp:24:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0;i<aparece[outra].size();i++){
                   ^
roz.cpp:26:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(i + 1 == aparece[outra].size()) proxima = N;
              ^
roz.cpp:9:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
                ^
roz.cpp:12:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf(" %c",&c);
                  ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9832 KB Output is correct
2 Correct 0 ms 9832 KB Output is correct
3 Correct 0 ms 9832 KB Output is correct
4 Correct 0 ms 9832 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9832 KB Output is correct
2 Correct 0 ms 9832 KB Output is correct
3 Correct 0 ms 9832 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9832 KB Output is correct
2 Correct 0 ms 9832 KB Output is correct
3 Correct 0 ms 9832 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 9832 KB Output is correct
2 Correct 0 ms 9832 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9964 KB Output is correct
2 Correct 0 ms 9832 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 10240 KB Output is correct
2 Correct 0 ms 9832 KB Output is correct
3 Correct 5 ms 9964 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 248 ms 17260 KB Output is correct
2 Correct 0 ms 9832 KB Output is correct
3 Correct 177 ms 14408 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 16908 KB Output is correct
2 Correct 198 ms 16384 KB Output is correct
3 Correct 159 ms 16612 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 17256 KB Output is correct
2 Correct 191 ms 17092 KB Output is correct
3 Correct 220 ms 15064 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 16856 KB Output is correct
2 Correct 203 ms 15040 KB Output is correct
3 Correct 219 ms 17128 KB Output is correct