Submission #448609

#	Time	Username	Problem	Language	Result	Execution time	Memory
448609		Killer2501	Miners (IOI07_miners)	C++14	100 / 100	217 ms	116864 KiB

miners

#include <bits/stdc++.h>
using namespace std;
#define ll int
#define pll pair<ll, ll>
#define fi first
#define se second
#define pb push_back

const int N = 1e5+5;
const ll mod = 1e9;
const int base = 300;

ll m, n, t, k, a[N], ans, b[N], tong, d[N], lab[N], cnt, c[N], dp[N][4][4][4][4];
vector<ll> adj[N];
vector<pll> ask[N];
vector<pll> kq, val;

string s;
ll pw(ll k, ll n)
{
    ll total = 1;
    for(; n; n >>= 1)
    {
        if(n & 1)total = total * k % mod;
        k = k * k % mod;
    }
    return total;
}

ll cal(ll i, ll mine11, ll mine12, ll mine21, ll mine22)
{
    if(i > n)return 0;
    if(dp[i][mine11][mine12][mine21][mine22] != -1)return dp[i][mine11][mine12][mine21][mine22];
    ll res = 0;
    ll cost = 1;
    if(mine11 != 0 && mine11 != a[i])
    {
        cost = 2;
        if(mine12 != 0 && mine12 != a[i] && mine12 != mine11)cost = 3;
    }
    else if(mine12 != 0 && mine12 != a[i])cost = 2;
    res = max(res, cal(i+1, mine12, a[i], mine21, mine22) + cost);
    cost = 1;
    if(mine21 != 0 && mine21 != a[i])
    {
        cost = 2;
        if(mine22 != 0 && mine22 != a[i] && mine22 != mine21)cost = 3;
    }
    else if(mine22 != 0 && mine22 != a[i])cost = 2;
    res = max(res, cal(i+1, mine11, mine12, mine22, a[i]) + cost);
    return dp[i][mine11][mine12][mine21][mine22] = res;
}
void sol()
{
    cin >> n >> s;
    for(int i = 1; i <= n; i ++)
    {
        if(s[i-1] == 'M')a[i] = 1;
        else if(s[i-1] == 'F')a[i] = 2;
        else a[i] = 3;
    }
    memset(dp, -1, sizeof(dp));
    cout << cal(1, 0, 0, 0, 0);
}
int main()
{
    cin.tie(0);
    cout.tie(0);
    ios_base::sync_with_stdio(0);
    #define task "tests"

    if(fopen(task".in", "r"))
    {
        freopen(task".in", "r", stdin);
        //freopen(task".out", "w", stdout);
    }
    int ntest = 1;
    //cin >> ntest;
    while(ntest -- > 0)
    sol();
}
/*
4
1
8
2 1 3 5 1 2 4 5
15
16384 8192 4096 2048 1024 512 256 128 64 32 16 8 4 2 1
2
3 3
14
1 2 3 4 5 6 7 8 9 10 11 12 13 14

*/

Compilation message (stderr)

miners.cpp: In function 'int main()':
miners.cpp:74:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   74 |         freopen(task".in", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• 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