Submission #863867

#TimeUsernameProblemLanguageResultExecution timeMemory
863867VN_AnhTuanPalinilap (COI16_palinilap)C++14
0 / 100
1059 ms2392 KiB
#include <bits/stdc++.h> #define fi first #define se second #define pii pair<int, int> #define mp make_pair #define pb push_back #define bit(X,i) ((X>>i)&1) #define fori(i,d,c) for(int i = d; i <= c; ++ i) #define ford(i,d,c) for(int i = d; i >= c; -- i) #define all(V) V.begin(), V.end() #define RRH(V) V.resize(unique(all(V))-V.begin()) #define Task "palival" using namespace std; using ll = long long; using ld = long double; const int maxn = 1e5 + 5; const int maxm = 1e6 + 5; const int base = 101; string s; int n; void read() { cin >> s; n = s.size(); s = " " + s; } namespace sub1{ int f[105][105]; int calc() { ford(i,n,1) { fori(j,i,n) { if (j == i) f[i][j] = 1; else { if (s[i] == s[j]) { if (i + 1 == j) f[i][j] = 1; else f[i][j] = f[i+1][j-1]; } else f[i][j] = 0; } } } int res = 0; fori(i,1,n) fori(j,i,n) res += f[i][j]; return res; } void solve() { int res = calc(); fori(i,1,n) { char c = s[i]; fori(j,0,25) { if (s[i] - 'a' == j) continue; s[i] = char(j + 'a'); // if(calc() > res) { // cout << i << ' ' << s[i] << '\n'; // } res = max(res, calc()); } s[i] = c; } cout << res; } } ll Total_Result; namespace tester { int f[5005][5005]; int calc() { ford(i,n,1) { fori(j,i,n) { if (j == i) f[i][j] = 1; else { if (s[i] == s[j]) { if (i + 1 == j) f[i][j] = 1; else f[i][j] = f[i+1][j-1]; } else f[i][j] = 0; } } } int res = 0; fori(i,1,n) fori(j,i,n) res += f[i][j]; return res; } void solve() { int cs = -1, sum = 0; fori(i,2,n-1) { if (s[i-1] == s[i+1]) { int j = i-1; while(j - 1 >= 1 && s[j-1] == s[j]) j --; int j1 = i+1; while(j1 + 1 <= n && s[j1 + 1] == s[j1]) j1 ++; if (j1 - j + 1 > sum) { cs = i; sum = j1 - j + 1; } } } int res = calc(); if (1){ int sum1 = 0; int cs1 = 0, cs2 = n + 1; for(int i = 1; i <= n;) { int j1 = i; while(j1 + 1 <= n && s[j1 + 1] == s[i]) j1 ++; if (sum1 < j1 - i + 1) { sum1 = j1 - i + 1; cs1 = i - 1; cs2 = j1 + 1; } i = j1 + 1; } if (cs1 >= 1) { char c = s[cs1]; s[cs1] = s[cs1 + 1]; res = max(res, calc()); s[cs1] = c; } if (cs2 <= n) { char c = s[cs2]; s[cs2] = s[cs2-1]; res = max(res, calc()); s[cs2] = c; } Total_Result = max(Total_Result, 1ll * res); } if (cs != -1){ s[cs] = s[cs-1]; res = max(res, calc()); Total_Result = max(Total_Result, 1ll * res); } } } namespace sub2 { int f[5005][5005]; int calc() { ford(i,n,1) { fori(j,i,n) { if (j == i) f[i][j] = 1; else { if (s[i] == s[j]) { if (i + 1 == j) f[i][j] = 1; else f[i][j] = f[i+1][j-1]; } else f[i][j] = 0; } } } int res = 0; fori(i,1,n) fori(j,i,n) res += f[i][j]; return res; } int dif(int i, int j) { int cnt = 0; while(i <= j) { if (s[i] != s[j]) { cnt ++; } i ++; j --; } return cnt; } void solve() { int sum = 0, cs1 = 0, cs2 = 0; fori(i,1,n) fori(j,i,n){ if (dif(i,j) <= 1) { if (sum < j - i + 1) { sum = j - i + 1; cs1 = i; cs2 = j; } } } int res = calc(); while(cs1 <= cs2) { if (s[cs1] != s[cs2]) { char c = s[cs1]; s[cs1] = s[cs2]; res = max(res, calc()); s[cs1] = c; s[cs2] = s[cs1]; res = max(res, calc()); break; } cs1 ++; cs2 --; } cout << res; } } void solve() { Total_Result = n; // if (n <= 100) sub1::solve(); // else { // tester::solve(); // cout << Total_Result; // } sub2::solve(); } int main () { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen(Task".inp", "r")) { freopen(Task".inp", "r", stdin); freopen(Task".out", "w", stdout); } read(); solve(); cerr << "\nTime elapsed: " << 1000 * clock() / CLOCKS_PER_SEC << "ms\n"; return 0; }

Compilation message (stderr)

palinilap.cpp: In function 'int main()':
palinilap.cpp:210:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  210 |         freopen(Task".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
palinilap.cpp:211:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  211 |         freopen(Task".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...