oj.uz

답안 #91510

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
91510 2018-12-28T02:05:21 Z jasony123123 Palinilap (COI16_palinilap) C++11
100 / 100
 94 ms 28784 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
//#include <ext/pb_ds/tree_policy.hpp>
//#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;

#define FOR(i,start,end) for(int i=start;i<(int)(end);i++)
#define FORE(i,start,end) for(int i=start;i<=(int)end;i++)
#define RFOR(i,start,end) for(int i = start; i>end; i--)
#define RFORE(i,start,end) for(int i = start; i>=end; i--)
#define all(a) a.begin(), a.end()
#define mt make_tuple
#define mp make_pair
#define v vector
#define sf scanf
#define pf printf
#define dvar(x) cout << #x << " := " << x << "\n"
#define darr(x,n) FOR(i,0,n) cout << #x << "[" << i << "]" << " := " << x[i] << "\n"

typedef long long ll;
typedef long double ld;
typedef pair<int, int > pii;
typedef pair<ll, ll> pll;
//template <class T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<class T> void minn(T &a, T b) { a = min(a, b); }
template<class T> void maxx(T &a, T b) { a = max(a, b); }

void io() {
#ifdef LOCAL_PROJECT 
	freopen("input.in", "r", stdin); freopen("output.out", "w", stdout);
#else 
	/* online submission */

#endif 
	ios_base::sync_with_stdio(false); cin.tie(NULL);
}

#define MOD 2038072819LL
#define PRI 610639LL
const ll INF = 1e18;
/****************************************************************/

const int MAXN = 100099;
string S;
int N;

ll p[MAXN];
ll forHash[MAXN], revHash[MAXN];

inline ll getfh(int a, int b) {
	return (MOD + forHash[b] - (a == 0 ? 0 : forHash[a - 1])) % MOD;
}
inline ll getrh(int a, int b) {
	return (MOD + revHash[b] - (a == 0 ? 0 : revHash[a - 1])) % MOD;
}
inline bool equ(int a, int b, int c, int d) { // test a<-b == c->d
	return (getrh(a, b) * p[b]) % MOD == (getfh(c, d) * p[N - 1 - c]) % MOD;
}

inline void computeHash() {
	p[0] = 1;
	FOR(i, 1, N) p[i] = (PRI*p[i - 1]) % MOD;
	FOR(i, 0, N) {
		forHash[i] = ((ll)S[i] * p[i]) % MOD;
		if (i) forHash[i] = (forHash[i] + forHash[i - 1]) % MOD;
	}
	FOR(i, 0, N) {
		revHash[i] = ((ll)S[i] * p[N - 1 - i]) % MOD;
		if (i) revHash[i] = (revHash[i] + revHash[i - 1]) % MOD;
	}
}

ll lval[MAXN], lcnt[MAXN], rval[MAXN], rcnt[MAXN];
ll add[MAXN][26];

int main() {
	io();
	cin >> S;
	N = S.length();
	computeHash();

	ll total = 0;
	FOR(i, 0, N) FORE(j, i, min(i + 1, N - 1)) {
		// binary search for largest palindrom l->i j->r
		int lo = 0, hi = min(i + 1, N - j);
		while (lo < hi) {
			int mid = (lo + hi + 1) / 2;
			if (equ(i - mid + 1, i, j, j + mid - 1)) lo = mid;
			else hi = mid - 1;
		}
		int sz = lo;
		int l = i - sz + 1, r = j + sz - 1;
		total += sz;
	//	if (lo != 0)
	//		pf("%d-%d-%d-%d\n", l, i, j, r);
		if (i == j && sz > 1) {
			lval[l] += l, lcnt[l] += 1;
			lval[i] -= l, lcnt[i] -= 1;
			rval[i + 1] += r, rcnt[i + 1] += 1;
			rval[r + 1] -= r, rcnt[r + 1] -= 1;
		}
		else if(i!=j && sz>0){
			lval[l] += l, lcnt[l] += 1;
			lval[j] -= l, lcnt[j] -= 1;
			rval[j] += r, rcnt[j] += 1;
			rval[r + 1] -= r, rcnt[r + 1] -= 1;
		}


		int x = l - 1, y = r + 1;
		if (x < 0 || y >= N) continue;
		lo = 0, hi = min(x, N - y - 1);
		while (lo < hi) {
			int mid = (lo + hi + 1) / 2;
			if (equ(x - mid, x - 1, y + 1, y + mid)) lo = mid;
			else hi = mid - 1;
		}
		add[x][S[y] - 'a'] += lo + 1;
		add[y][S[x] - 'a'] += lo + 1;
	}

	ll lv = 0, lc = 0, rv = 0, rc = 0;
	ll best = 0;
	FOR(i, 0, N) {
		ll diff = 0;
		lv += lval[i];
		lc += lcnt[i];
		rv += rval[i];
		rc += rcnt[i];
		diff -= ((ll)i + 1LL)*lc - lv;
		diff -= rv + rc*(1LL - (ll)i);
		FOR(c, 0, 26) if(c!=S[i]-'a')
			maxx(best, diff + add[i][c]);
	}
	cout << total + best << "\n";
	return 0;
}

Subtask #1
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 556 KB Output is correct
3 Correct 2 ms 672 KB Output is correct
4 Correct 2 ms 704 KB Output is correct
5 Correct 2 ms 704 KB Output is correct

Subtask #2
37.0 / 37.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 1988 KB Output is correct
2 Correct 4 ms 2124 KB Output is correct
3 Correct 5 ms 2124 KB Output is correct
4 Correct 3 ms 2124 KB Output is correct
5 Correct 4 ms 2124 KB Output is correct
6 Correct 5 ms 2124 KB Output is correct
7 Correct 5 ms 2136 KB Output is correct

Subtask #3
46.0 / 46.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 27012 KB Output is correct
2 Correct 60 ms 27076 KB Output is correct
3 Correct 63 ms 27192 KB Output is correct
4 Correct 82 ms 27316 KB Output is correct
5 Correct 82 ms 27348 KB Output is correct
6 Correct 80 ms 27460 KB Output is correct
7 Correct 81 ms 27580 KB Output is correct
8 Correct 39 ms 27580 KB Output is correct
9 Correct 82 ms 27788 KB Output is correct
10 Correct 81 ms 27884 KB Output is correct
11 Correct 61 ms 27984 KB Output is correct
12 Correct 89 ms 28212 KB Output is correct
13 Correct 94 ms 28212 KB Output is correct
14 Correct 79 ms 28260 KB Output is correct
15 Correct 76 ms 28408 KB Output is correct
16 Correct 94 ms 28484 KB Output is correct
17 Correct 79 ms 28520 KB Output is correct
18 Correct 77 ms 28684 KB Output is correct
19 Correct 75 ms 28784 KB Output is correct