oj.uz

Submission #448609

# Submission time Handle Problem Language Result Execution time Memory
448609 2021-07-31T07:27:47 Z Killer2501 Miners (IOI07_miners) C++14
100 / 100
 217 ms 116864 KB 
#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

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

# Verdict Execution time Memory Grader output
1 Correct 48 ms 105172 KB Output is correct

Subtask #2
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 105156 KB Output is correct

Subtask #3
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 105192 KB Output is correct

Subtask #4
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 105088 KB Output is correct

Subtask #5
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 105092 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 105208 KB Output is correct

Subtask #7
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 50 ms 105236 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 105700 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 106256 KB Output is correct

Subtask #10
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 108076 KB Output is correct

Subtask #11
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 166 ms 114052 KB Output is correct

Subtask #12
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 217 ms 116864 KB Output is correct