Submission #109114

#	Time	Username	Problem	Language	Result	Execution time	Memory
109114		MetB	Miners (IOI07_miners)	C++14	92 / 100	1568 ms	5312 KiB

miners

#include <iostream>
#include <cstdlib>
#include <string>
#include <set>
#include <map>
#include <algorithm>
#include <bitset>
#include <queue>
#include <math.h>
#include <stack>
#include <vector>
#include <string.h>
#include <random>
 
typedef long long ll;
 
const ll MOD = 1e9 + 7, INF = 1e18;
 
using namespace std;
 
int n;
 
pair <string, int> transfer (pair <string, int> s, char a)
{
	string t;
	s.first += a;
 
	string k = s.first;
 
	k += a;
 
	sort (k.begin(), k.end());
 
	int v = k.length ();
 
	for (int i = 0; i < k.length (); i++)
		if (k[i] == k[i-1]) v--;
 
	if (s.first.length () == 3)
		for (int i = 1; i < s.first.length (); i++)
			t += s.first[i];
	else t = s.first;
 
	return {t, v + s.second};
}
 
map < pair <string, string> , int> d[100000];
 
int main ()
{
	cin >> n;
 
	string s;
 
	cin >> s;
 
	string h (1, s[0]);
 
	d[0][{h, ""}] = 1;
 
	int mx = 0;
 
	for (int i = 1; i < s.length (); i++)
	{
		for (auto it : d[i-1])
		{
			auto k1 = transfer ({it.first.first, it.second}, s[i]);
			auto k2 = transfer ({it.first.second, it.second}, s[i]);
 
			mx = max (mx, k1.second);
			mx = max (mx, k2.second);
 
			auto v = d[i].find (make_pair (k1.first, it.first.second));
			if (v == d[i].end ()) d[i][make_pair (k1.first, it.first.second)] = k1.second;
			else d[i][make_pair (k1.first, it.first.second)] = max (k1.second, v -> second);
 
			v = d[i].find (make_pair (it.first.first, k2.first));
			if (v == d[i].end ()) d[i][make_pair (it.first.first, k2.first)] = k2.second;
			else d[i][make_pair (it.first.first, k2.first)] = max (k2.second, v -> second);
		}
 
		d[i-1].clear ();
	}
 
	cout << mx;
}

Compilation message (stderr)

miners.cpp: In function 'std::pair<std::__cxx11::basic_string<char>, int> transfer(std::pair<std::__cxx11::basic_string<char>, int>, char)':
miners.cpp:36:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < k.length (); i++)
                  ~~^~~~~~~~~~~~~
miners.cpp:40:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = 1; i < s.first.length (); i++)
                   ~~^~~~~~~~~~~~~~~~~~~
miners.cpp: In function 'int main()':
miners.cpp:63:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 1; i < s.length (); i++)
                  ~~^~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 9 / 9
• Subtask 3: 9 / 9
• Subtask 4: 9 / 9
• Subtask 5: 9 / 9
• Subtask 6: 7 / 7
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 8 / 8
• Subtask 11: 8 / 8
• Subtask 12: 0 / 8