Submission #421747

#	Time	Username	Problem	Language	Result	Execution time	Memory
421747		SAAD	Miners (IOI07_miners)	C++17	100 / 100	959 ms	155796 KiB

miners

#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 (stderr)

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];
      |                    ^

• 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: 8 / 8