| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 109117 |
2019-05-04T12:03:03 Z |
MetB |
Miners (IOI07_miners) |
C++14 |
|
1500 ms |
150828 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;
int enc (string a)
{
if (a == "") return 0;
if (a == "M") return 1;
if (a == "B") return 2;
if (a == "F") return 3;
if (a == "MM") return 4;
if (a == "MB") return 5;
if (a == "MF") return 6;
if (a == "BM") return 7;
if (a == "BB") return 8;
if (a == "BF") return 9;
if (a == "FM") return 10;
if (a == "FB") return 11;
if (a == "FF") return 12;
}
string dec (int a)
{
if (a == 0) return "";
if (a == 1) return "M";
if (a == 2) return "B";
if (a == 3) return "F";
if (a == 4) return "MM";
if (a == 5) return "MB";
if (a == 6) return "MF";
if (a == 7) return "BM";
if (a == 8) return "BB";
if (a == 9) return "BF";
if (a == 10) return "FM";
if (a == 11) return "FB";
if (a == 12) return "FF";
}
int encode (pair <string, string> s)
{
return enc (s.first) * 13 + enc (s.second);
}
pair <string, string> decode (int s)
{
return make_pair (dec (s / 13), dec (s % 13));
}
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};
}
int d[100000][256], u[100000][256];
int main ()
{
cin >> n;
string s;
cin >> s;
string h (1, s[0]);
d[1][encode ({h, ""})] = 1;
u[1][encode ({h, ""})] = 1;
int mx = 0;
for (int i = 1; i < s.length (); i++)
{
for (int j = 0; j < 169; j++)
{
if (!u[i][j]) continue;
auto sd = decode (j);
auto k1 = transfer ({sd.first, d[i][j]}, s[i]);
auto k2 = transfer ({sd.second, d[i][j]}, s[i]);
mx = max (mx, k1.second);
mx = max (mx, k2.second);
int new_j = encode (make_pair (k1.first, sd.second));
u[i + 1][new_j] = 1;
d[i + 1][new_j] = max (d[i + 1][new_j], k1.second);
new_j = encode (make_pair (sd.first, k2.first));
u[i + 1][new_j] = 1;
d[i + 1][new_j] = max (d[i + 1][new_j], k2.second);
}
}
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:80:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < k.length (); i++)
~~^~~~~~~~~~~~~
miners.cpp:84: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:108:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 1; i < s.length (); i++)
~~^~~~~~~~~~~~~
miners.cpp: In function 'int enc(std::__cxx11::string)':
miners.cpp:38:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
miners.cpp: In function 'std::__cxx11::string dec(int)':
miners.cpp:55:1: warning: control reaches end of non-void function [-Wreturn-type]
}
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
432 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
22 ms |
2304 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
49 ms |
10484 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
228 ms |
20384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
496 ms |
50460 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1186 ms |
150828 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1575 ms |
134516 KB |
Time limit exceeded |
