| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 421747 |
2021-06-09T11:39:37 Z |
SAAD |
Miners (IOI07_miners) |
C++17 |
|
959 ms |
155796 KB |
#define F first
#define S second
#define rep(i,a,b) for(int i=a;!(a==b&&i!=b)&&((i<=b&&b>=a)||(i>=b&&a>=b));i+=(a<=b?1:-1))
#define pb push_back
#define Fbitl __builtin_ffs
#define bit1 __builtin_popcount
#include <iostream>
#include <math.h>
#include <algorithm>
#include <string.h>
#include <vector>
#include <queue>
#include <map>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<string, string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<ll> vl;
typedef vector<vl> vvl;
int x[(int)1e5], n, dp[(int)1e5][4][4][4][4] ;
int whr[200];
string s(string a, char p) {
swap(a[0], a[2]);
swap(a[0], a[1]);
a[2] = p;
return a;
}
int gain(string a) {
bool hi[] = { 1 , 0 , 0 , 0 };
int res = 0;
for (auto i : a) {
res += (!hi[(int)i] ? 1 : 0);
hi[(int)i] = true;
}
return res;
}
int SAAD(int idx, string a, string b) {
int mx = 0;
if (idx == n)return 0;
if (dp[idx][a[1]][a[2]][b[1]][b[2]] != 0) return dp[idx][a[1]][a[2]][b[1]][b[2]];
mx = max(SAAD(idx + 1, s(a, char(x[idx])), b) + gain(s(a, char(x[idx]))), SAAD(idx + 1, a, s(b, char(x[idx]))) + gain(s(b, char(x[idx]))));
//cout << idx << " " << mx << endl << a << " " << b << endl ;
return dp[idx][a[1]][a[2]][b[1]][b[2]] = mx;
}
int main() {
char a;
whr['M'] = 1;
whr['B'] = 2;
whr['F'] = 3;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a;
x[i] = whr[a];
}
string h = { 0 , 0 , 0} ;
cout << SAAD(0,h,h);
return 0;
}
Compilation message
miners.cpp: In function 'int SAAD(int, std::string, std::string)':
miners.cpp:46:21: warning: array subscript has type 'char' [-Wchar-subscripts]
46 | if (dp[idx][a[1]][a[2]][b[1]][b[2]] != 0) return dp[idx][a[1]][a[2]][b[1]][b[2]];
| ^
miners.cpp:46:27: warning: array subscript has type 'char' [-Wchar-subscripts]
46 | if (dp[idx][a[1]][a[2]][b[1]][b[2]] != 0) return dp[idx][a[1]][a[2]][b[1]][b[2]];
| ^
miners.cpp:46:33: warning: array subscript has type 'char' [-Wchar-subscripts]
46 | if (dp[idx][a[1]][a[2]][b[1]][b[2]] != 0) return dp[idx][a[1]][a[2]][b[1]][b[2]];
| ^
miners.cpp:46:39: warning: array subscript has type 'char' [-Wchar-subscripts]
46 | if (dp[idx][a[1]][a[2]][b[1]][b[2]] != 0) return dp[idx][a[1]][a[2]][b[1]][b[2]];
| ^
miners.cpp:46:66: warning: array subscript has type 'char' [-Wchar-subscripts]
46 | if (dp[idx][a[1]][a[2]][b[1]][b[2]] != 0) return dp[idx][a[1]][a[2]][b[1]][b[2]];
| ^
miners.cpp:46:72: warning: array subscript has type 'char' [-Wchar-subscripts]
46 | if (dp[idx][a[1]][a[2]][b[1]][b[2]] != 0) return dp[idx][a[1]][a[2]][b[1]][b[2]];
| ^
miners.cpp:46:78: warning: array subscript has type 'char' [-Wchar-subscripts]
46 | if (dp[idx][a[1]][a[2]][b[1]][b[2]] != 0) return dp[idx][a[1]][a[2]][b[1]][b[2]];
| ^
miners.cpp:46:84: warning: array subscript has type 'char' [-Wchar-subscripts]
46 | if (dp[idx][a[1]][a[2]][b[1]][b[2]] != 0) return dp[idx][a[1]][a[2]][b[1]][b[2]];
| ^
miners.cpp:49:24: warning: array subscript has type 'char' [-Wchar-subscripts]
49 | return dp[idx][a[1]][a[2]][b[1]][b[2]] = mx;
| ^
miners.cpp:49:30: warning: array subscript has type 'char' [-Wchar-subscripts]
49 | return dp[idx][a[1]][a[2]][b[1]][b[2]] = mx;
| ^
miners.cpp:49:36: warning: array subscript has type 'char' [-Wchar-subscripts]
49 | return dp[idx][a[1]][a[2]][b[1]][b[2]] = mx;
| ^
miners.cpp:49:42: warning: array subscript has type 'char' [-Wchar-subscripts]
49 | return dp[idx][a[1]][a[2]][b[1]][b[2]] = mx;
| ^
miners.cpp: In function 'int main()':
miners.cpp:59:20: warning: array subscript has type 'char' [-Wchar-subscripts]
59 | x[i] = whr[a];
| ^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
300 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
332 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
9 ms |
1740 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
25 ms |
8056 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
102 ms |
15728 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
211 ms |
39088 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
533 ms |
116792 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
959 ms |
155796 KB |
Output is correct |
