제출 #166953

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
166953		DavidDamian	Miners (IOI07_miners)	C++11	100 / 100	828 ms	119564 KiB

miners

#include <bits/stdc++.h>
using namespace std;
///Dynamic Programming
///Determine the maximum amount of coal we can get from sending food
int n;
int memo[100005][4][4][4][4];
string s;
int convert(char c) ///Converts a character into a code
{
    if(c=='M') return 1;
    if(c=='F') return 2;
    if(c=='B') return 3;
}
int production(vector<int>& prev,int mine,int next) ///Determines how many coal are produced with a given shipments
{
    int a,b;
    if(mine==1)
        a=0,b=2;
    else
        a=2,b=4;
    short used[5];
    memset(used,0,sizeof(used));
    int total=0;
    for(int i=a;i<b;i++){
        if(prev[i]==0) continue;
        int food=prev[i];
        if(!used[food]){
            used[food]=1;
            total++;
        }
    }
    if(!used[next])
        total++;
    return total;
}
int coal(int i,vector<int> prev)
{
    if(i==n)
        return 0;
    int maximum=0;
    vector<int> next=prev;
    int food=convert(s[i]);
    if(memo[i][ prev[0] ][ prev[1] ][ prev[2] ][ prev[3] ]==0){ //If there are -1 does not store the answer
        int k=production(prev,1,food); //Obtains the amount of coal if the food was shipped to mine 1
        next[0]=prev[1];
        next[1]=food;
        maximum=max(maximum,coal(i+1,next)+k); //And we get the answer of that mine
        next[0]=prev[0];
        next[1]=prev[1];
        next[2]=prev[3];
        next[3]=food;
        k=production(prev,2,food);
        maximum=max(maximum,coal(i+1,next)+k); //Obtains the amount of coal if the food was shipped to mine 2
        memo[i][ prev[0] ][ prev[1] ][ prev[2] ][ prev[3] ]=maximum;
    }
    return memo[i][ prev[0] ][ prev[1] ][ prev[2] ][ prev[3] ];
}
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    cin>>n;
    cin>>s;
    vector<int> A;
    int food=convert(s[0]);
    A.push_back(0);
    A.push_back(food);
    A.push_back(0);
    A.push_back(0); //We always send food 1 to mine 1 because we obtain the same results sending it to both mines
    int total=coal(1,A)+1; //Because that we add one to the answer
    cout<<total<<'\n';
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

miners.cpp: In function 'int convert(char)':
miners.cpp:13:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• 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