Submission #166951

#	Time	Username	Problem	Language	Result	Execution time	Memory
166951		DavidDamian	Miners (IOI07_miners)	C++11	60 / 100	1583 ms	20584 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][3][3][3][3];
string s;
int convert(char c) ///Converts a character into a code
{
    if(c=='M') return 0;
    if(c=='F') return 1;
    if(c=='B') return 2;
}
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[4];
    memset(used,0,sizeof(used));
    int total=0;
    for(int i=a;i<b;i++){
        if(prev[i]==-1) 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;
    bool negative=false;
    for(int i=0;i<prev.size();i++){
        if(prev[i]==-1)
            negative=true;
    }
    int maximum=0;
    vector<int> next=prev;
    int food=convert(s[i]);
    if(negative){ //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); //Obtains the amount of coal if the food was shipped to mine 2
        maximum=max(maximum,coal(i+1,next)+k);
    }
    else{
        if(memo[i][ prev[0] ][ prev[1] ][ prev[2] ][ prev[3] ]==0){ //Same but storing the values
            int k=production(prev,1,food);
            next[0]=prev[1];
            next[1]=food;
            maximum=max(maximum,coal(i+1,next)+k);
            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);
            memo[i][ prev[0] ][ prev[1] ][ prev[2] ][ prev[3] ]=maximum;
        }
        maximum=memo[i][ prev[0] ][ prev[1] ][ prev[2] ][ prev[3] ];
    }
    return maximum;
}
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(-1);
    A.push_back(food);
    A.push_back(-1);
    A.push_back(-1); //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;
}

Compilation message (stderr)

miners.cpp: In function 'int coal(int, std::vector<int>)':
miners.cpp:41:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<prev.size();i++){
                 ~^~~~~~~~~~~~
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: 0 / 8
• Subtask 9: 0 / 8
• Subtask 10: 0 / 8
• Subtask 11: 0 / 8
• Subtask 12: 0 / 8