제출 #1201879

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1201879		vicvic	Miners (IOI07_miners)	C++20	100 / 100	557 ms	116892 KiB

miners

#include <iostream>
#include <string>
#include <cstring>
#include <set>
#include <vector>
using namespace std;
const int NMAX=1e5;
int n;
string input;
int v[NMAX+5];
int temp[NMAX+5];
int dp[NMAX+5][4][4][4][4];
int getVal (vector <int> vec)
{
    set <int> setul;
    for (auto chestie : vec)
        if (chestie) setul.insert (chestie);
    return setul.size();
}
int makeDP (int i, int a, int a1, int b, int b1)
{
    if (i==n)
        return 0;
    int &res=dp[i][a][a1][b][b1];
    if (res!=-1)
        return res;
    int rez1=getVal ({a1, a, v[i]});
    int rez2=getVal ({b, b1, v[i]});
    return res=max (rez1+makeDP (i+1, v[i], a, b, b1), rez2+makeDP (i+1, a, a1, v[i], b));
}
int main ()
{
    temp['M']=1;
    temp['B']=2;
    temp['F']=3;
    ios_base :: sync_with_stdio (0);
    cin.tie (nullptr);
    cin >> n;
    cin >> input;
    memset (dp, -1, sizeof(dp));
    for (int i=0;i<n;i++)
    {
        v[i]=temp[input[i]];
    }
    cout << makeDP (0, 0, 0, 0, 0);
    return 0;
}

• 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