oj.uz

Submission #108925

# Submission time Handle Problem Language Result Execution time Memory
108925 2019-05-02T20:48:30 Z MetB Miners (IOI07_miners) C++14
92 / 100
 1500 ms 5500 KB 
#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 << endl;
	}

	cout << mx;
}

Compilation message

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.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 4992 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 4992 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 4992 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 4992 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 274 ms 5112 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 623 ms 5120 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1391 ms 5500 KB Output is correct

Subtask #12
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1574 ms 5248 KB Time limit exceeded