Submission #1525807


Source Code Expand

Copy
#include <bits/stdc++.h>

using namespace std;
#define FOR(i,n) for(int i = 0; i < (n); i++)
#define sz(c) ((int)c.size())
#define ten(n) ((int)1e##n)
using ll = long long;
using Pii = pair<int, int>;
using Pll = pair<ll, ll>;

template<typename ...> static inline int getchar_unlocked(void) { return getchar(); }
template<typename ...> static inline void putchar_unlocked(int c) { putchar(c); }
#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)
void reader(int& x) { int k, m = 0; x = 0; for (;;) { mygc(k); if (k == '-') { m = 1; break; }if ('0' <= k&&k <= '9') { x = k - '0'; break; } }for (;;) { mygc(k); if (k<'0' || k>'9')break; x = x * 10 + k - '0'; }if (m) x = -x; }
void reader(ll& x) { int k, m = 0; x = 0; for (;;) { mygc(k); if (k == '-') { m = 1; break; }if ('0' <= k&&k <= '9') { x = k - '0'; break; } }for (;;) { mygc(k); if (k<'0' || k>'9')break; x = x * 10 + k - '0'; }if (m) x = -x; }
int reader(char c[]) { int i, s = 0; for (;;) { mygc(i); if (i != ' '&&i != '\n'&&i != '\r'&&i != '\t'&&i != EOF) break; }c[s++] = i; for (;;) { mygc(i); if (i == ' ' || i == '\n' || i == '\r' || i == '\t' || i == EOF) break; c[s++] = i; }c[s] = '\0'; return s; }
int reader(string& c) { int i; for (;;) { mygc(i); if (i != ' '&&i != '\n'&&i != '\r'&&i != '\t'&&i != EOF) break; }c.push_back(i); for (;;) { mygc(i); if (i == ' ' || i == '\n' || i == '\r' || i == '\t' || i == EOF) break; c.push_back(i); }; return sz(c); }
template <class T, class S> void reader(T& x, S& y) { reader(x); reader(y); }
template <class T, class S, class U> void reader(T& x, S& y, U& z) { reader(x); reader(y); reader(z); }
template <class T, class S, class U, class V> void reader(T& x, S& y, U& z, V & w) { reader(x); reader(y); reader(z); reader(w); }
void writer(int x, char c) { int s = 0, m = 0; char f[10]; if (x<0)m = 1, x = -x; while (x)f[s++] = x % 10, x /= 10; if (!s)f[s++] = 0; if (m)mypc('-'); while (s--)mypc(f[s] + '0'); mypc(c); }
void writer(ll x, char c) { int s = 0, m = 0; char f[20]; if (x<0)m = 1, x = -x; while (x)f[s++] = x % 10, x /= 10; if (!s)f[s++] = 0; if (m)mypc('-'); while (s--)mypc(f[s] + '0'); mypc(c); }
void writer(const char c[]) { int i; for (i = 0; c[i] != '\0'; i++)mypc(c[i]); }
void writer(const string& x, char c) { int i; for (i = 0; x[i] != '\0'; i++)mypc(x[i]); mypc(c); }
void writer(const char x[], char c) { int i; for (i = 0; x[i] != '\0'; i++)mypc(x[i]); mypc(c); }
template<class T> void writerLn(T x) { writer(x, '\n'); }
template<class T, class S> void writerLn(T x, S y) { writer(x, ' '); writer(y, '\n'); }
template<class T, class S, class U> void writerLn(T x, S y, U z) { writer(x, ' '); writer(y, ' '); writer(z, '\n'); }
template<class T> void writerArr(T x[], int n) { if (!n) { mypc('\n'); return; }FOR(i, n - 1)writer(x[i], ' '); writer(x[n - 1], '\n'); }
template<class T> void writerArr(vector<T>& x) { writerArr(x.data(), (int)x.size()); }

template<class T> void chmin(T& a, const T& b) { if (a > b) a = b; }
template<class T> void chmax(T& a, const T& b) { if (a < b) a = b; }

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }
template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; }
ll mod_pow(ll a, ll n, ll mod) {
	ll ret = 1;
	ll p = a % mod;
	while (n) {
		if (n & 1) ret = ret * p % mod;
		p = p * p % mod;
		n >>= 1;
	}
	return ret;
}
template<class T> T extgcd(T a, T b, T& x, T& y) { for (T u = y = 1, v = x = 0; a;) { T q = b / a; swap(x -= q * u, u); swap(y -= q * v, v); swap(b -= q * a, a); } return b; }
template<class T> T mod_inv(T a, T m) { T x, y; extgcd(a, m, x, y); return (m + x % m) % m; }

const int MOD = ten(9) + 7;

bool chmin(int& a, int b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}

bool chmin(Pii& a, Pii b) {
	if (a > b) {
		a = b;
		return true;
	}
	return false;
}


Pii dp[ten(5) * 2 + 10][26];

int main() {
	memset(dp, 0x2f, sizeof(dp));
	FOR(i, 26) dp[0][i].first = 1, dp[0][i].second = 0;

	string s; reader(s);
	reverse(s.begin(), s.end());
	FOR(i, sz(s)) {
		FOR(j, 26) FOR(k, 26) {
			Pii nxt;
			if (j == k) {
				if (s[i] == 'a' + j) {
					nxt.first = dp[i][j].first + 1;
				} else {
					nxt.first = dp[i][j].first;
				}
			} else {
				nxt.first = dp[i][j].first + 1;
			}
			nxt.second = j;
			chmin(dp[i + 1][k], nxt);
		}
	}

	int idx = -1, mn = sz(s);
	FOR(i, 26) {
		if (chmin(mn, dp[sz(s)][i].first)) {
			idx = i;
		}
	}

	string ans;
	for (int i = sz(s); i > 0; i--) {
		int p = dp[i][idx].second;
		if (dp[i - 1][p].first != dp[i][idx].first) {
			ans.push_back('a' + idx);
		}
		idx = p;
	}
	ans.push_back('a' + idx);
	cout << ans << endl;

	return 0;
}

Submission Info

Submission Time
Task E - Don't Be a Subsequence
User math
Language C++14 (GCC 5.4.1)
Score 0
Code Size 4745 Byte
Status
Exec Time 433 ms
Memory 41220 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample1.txt, sample2.txt, sample3.txt
All 0 / 600 sample1.txt, sample2.txt, sample3.txt, 1.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 2.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 3.txt, 30.txt, 4.txt, 5.txt, 6.txt, 7.txt, 8.txt, 9.txt, sample1.txt, sample2.txt, sample3.txt
Case Name Status Exec Time Memory
1.txt 12 ms 40832 KB
10.txt 392 ms 41220 KB
11.txt 392 ms 41220 KB
12.txt 390 ms 41220 KB
13.txt 392 ms 41220 KB
14.txt 392 ms 41220 KB
15.txt 392 ms 41220 KB
16.txt 391 ms 41220 KB
17.txt 407 ms 41220 KB
18.txt 412 ms 41220 KB
19.txt 424 ms 41220 KB
2.txt 14 ms 40832 KB
20.txt 431 ms 41220 KB
21.txt 432 ms 41220 KB
22.txt 432 ms 41220 KB
23.txt 433 ms 41220 KB
24.txt 368 ms 41220 KB
25.txt 353 ms 41220 KB
26.txt 352 ms 41220 KB
27.txt 349 ms 41220 KB
28.txt 356 ms 41220 KB
29.txt 351 ms 41220 KB
3.txt 31 ms 40832 KB
30.txt 338 ms 41220 KB
4.txt 31 ms 40832 KB
5.txt 200 ms 41088 KB
6.txt 200 ms 41088 KB
7.txt 392 ms 41220 KB
8.txt 391 ms 41220 KB
9.txt 392 ms 41220 KB
sample1.txt 12 ms 40832 KB
sample2.txt 12 ms 40832 KB
sample3.txt 12 ms 40832 KB