Submission #3589727


Source Code Expand

#include <iostream>
#include <fstream>
#include <cmath>  
#include <cstdlib>
#include <ctime>
#include <algorithm>
#include <numeric>
#include <functional>
#include <string> 
#include <vector>
#include <bitset>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <deque>

using namespace std;
using ll = long long;

template<class T> using V = vector<T>;
template<class T, class U> using P = pair<T, U>;

#define REP(i,n) for(int i = 0; i < int(n); i++)
#define FOR(i, m, n) for(int i = int(m);i < int(n);i++)
#define ALL(obj) (obj).begin(),(obj).end()

const ll MOD = (ll)1e9 + 7;
const ll HINF = (ll)1e18;
const ll LINF = (ll)1e9;
const long double PI = 3.1415926535897932384626433;

vector<int> dy = { 0,0,1,-1 };
vector<int> dx = { 1,-1,0,0 };

template<class T> void corner(bool flg, T hoge) {
	if (flg) {
		cout << hoge << endl;
		exit(0);
	}
	else return;
}

template <class T, class U>ostream &operator<<(ostream &o, const map<T, U>&obj) {
	o << "{"; for (auto &x : obj) o << " {" << x.first << " : " << x.second << "}" << ","; o << " }"; return o;
}

template <class T>ostream &operator<<(ostream &o, const set<T>&obj) {
	o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr) o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;
}

template <class T>ostream &operator<<(ostream &o, const vector<T>&obj) {
	o << "{"; for (int i = 0; i < (int)obj.size(); ++i)o << (i > 0 ? ", " : "") << obj[i]; o << "}"; return o;
}

template <class T, class U>ostream &operator<<(ostream &o, const pair<T, U>&obj) {
	o << "{" << obj.first << ", " << obj.second << "}"; return o;
}

template <template <class tmp>  class T, class U> ostream &operator<<(ostream &o, const T<U> &obj) {
	o << "{"; for (auto itr = obj.begin(); itr != obj.end(); ++itr)o << (itr != obj.begin() ? ", " : "") << *itr; o << "}"; return o;
}

void print(void) {
	cout << endl;
}

template <class Head> void print(Head&& head) {
	cout << head;
	print();
}

template <class Head, class... Tail> void print(Head&& head, Tail&&... tail) {
	cout << head << " ";
	print(forward<Tail>(tail)...);
}

void YN(bool flg) {
	cout << ((flg) ? "YES" : "NO") << endl;
}

void Yn(bool flg) {
	cout << ((flg) ? "Yes" : "No") << endl;
}

void yn(bool flg) {
	cout << ((flg) ? "yes" : "no") << endl;
}


int main() {
	string s; cin >> s;
	s = "." + s + ".";

	int N = s.size();

	V<V< int >> edge(N, V< int >(26, LINF));
	V<P<int, string>> dp(N, { LINF,"" });

	int idx;
	REP(i,26){
		char ch = char(int(i + 'a'));
		idx = N-1;
		for (int j = N-2; 0 <= j; --j) {
			edge[j][i] = idx;
			if (s[j] == ch)idx = j;
		}
	}

	dp[0] = { 0,"" };

	REP(i,N-1){
		REP(j,26){
			int cnt = dp[i].first+1;
			char ch = char(int(j + 'a'));
			string str = dp[i].second;
			dp[i].second = "";
			dp[i].second.shrink_to_fit();
			str.push_back(ch);
			int to = edge[i][j];
			if ((cnt < dp[to].first) || (cnt == dp[to].first && str < dp[to].second)) {
				dp[to].first = cnt;
				dp[to].second = str;
			}
		}
	}

	cout << dp[N-1].second << endl;
	return 0;
}

Submission Info

Submission Time
Task E - Don't Be a Subsequence
User ningenMe
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3168 Byte
Status WA
Exec Time 718 ms
Memory 40256 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 600
Status
AC × 2
WA × 1
AC × 5
WA × 31
Set Name Test Cases
Sample sample1.txt, sample2.txt, sample3.txt
All 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 WA 2 ms 256 KB
10.txt WA 718 ms 39488 KB
11.txt WA 647 ms 39488 KB
12.txt WA 644 ms 39232 KB
13.txt WA 649 ms 39488 KB
14.txt WA 648 ms 39488 KB
15.txt WA 650 ms 39488 KB
16.txt WA 651 ms 39488 KB
17.txt WA 646 ms 39488 KB
18.txt WA 646 ms 39488 KB
19.txt WA 649 ms 39488 KB
2.txt WA 4 ms 384 KB
20.txt WA 657 ms 39488 KB
21.txt WA 654 ms 39488 KB
22.txt WA 691 ms 39488 KB
23.txt AC 652 ms 39488 KB
24.txt WA 649 ms 39488 KB
25.txt WA 705 ms 39488 KB
26.txt WA 645 ms 39488 KB
27.txt WA 645 ms 39488 KB
28.txt WA 699 ms 39488 KB
29.txt WA 645 ms 39616 KB
3.txt WA 31 ms 2176 KB
30.txt WA 644 ms 39488 KB
4.txt WA 31 ms 2176 KB
5.txt WA 308 ms 19836 KB
6.txt WA 382 ms 19836 KB
7.txt WA 645 ms 39488 KB
8.txt WA 640 ms 39488 KB
9.txt WA 643 ms 40256 KB
sample1.txt AC 1 ms 256 KB
sample2.txt AC 1 ms 256 KB
sample3.txt WA 2 ms 256 KB