oj.uz

Submission #30070

# Submission time Handle Problem Language Result Execution time Memory
30070 2017-07-22T04:32:59 Z 박상수(#1251) Difference (POI11_roz) C++11
100 / 100
 526 ms 14332 KB 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <memory.h>
#include <math.h>
#include <assert.h>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <algorithm>
#include <iostream>
#include <functional>
#include <unordered_map>
#include <unordered_set>
#include <list>
#include <bitset>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
#define Fi first
#define Se second
#define pb(x) push_back(x)
#define sz(x) ((int)(x).size())
#define rep(i, n) for(int i=0;i<n;i++)
#define all(x) (x).begin(), (x).end()
typedef tuple<int, int, int> t3;
typedef pair<ll, ll> pll;
typedef long double ldouble;
typedef pair<double, double> pdd;

int n;
char A[1000010];
vector <int> P[26];
int V[1000010], z;

void solve(){
	scanf("%d", &n);
	scanf("%s", A+1);
	for(int i=1;i<=n;i++) {
		int c = A[i] - 'a';
		P[c].pb(i);
	}
	int ans = 0;
	rep(i, 26) rep(j, i) {
		z = 0;
		for(int a=0, b=0;a<=sz(P[i]);a++) {
			while(b < sz(P[j]) && (a == sz(P[i]) || P[j][b] < P[i][a])) {
				V[++z] = -1; ++b;
			}
			if(a < sz(P[i]))V[++z] = 1;
		}
		int mn = 1e9, mx = -1e9;
		for(int a=1;a<=z;a++) V[a] += V[a-1];
		for(int a=1, b=0;a<=z;a++) {
			ans = max({ans, V[a] - mn, mx - V[a]});
			if(V[a]-V[a-1] != V[a+1]-V[a]) {
				while(b<a){
					if(mn > V[b]) mn = V[b];
					if(mx < V[b]) mx = V[b];
					++b;
				}
			}
		}
	}
	printf("%d\n", ans);
}

int main(){
	int T = 1; // scanf("%d", &T);
	while(T--) {
		solve();
	}
	
	return 0;
}

Compilation message

roz.cpp: In function 'void solve()':
roz.cpp:39:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
roz.cpp:40:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", A+1);
                  ^

Subtask #1
10.0 / 10.0

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

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 43 ms 7312 KB Output is correct
2 Correct 0 ms 6904 KB Output is correct
3 Correct 3 ms 7036 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 466 ms 14332 KB Output is correct
2 Correct 0 ms 6904 KB Output is correct
3 Correct 343 ms 11480 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 496 ms 13980 KB Output is correct
2 Correct 376 ms 13456 KB Output is correct
3 Correct 176 ms 13684 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 526 ms 14328 KB Output is correct
2 Correct 233 ms 14164 KB Output is correct
3 Correct 209 ms 12136 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 509 ms 13928 KB Output is correct
2 Correct 219 ms 12112 KB Output is correct
3 Correct 199 ms 14200 KB Output is correct