Cod sursa(job #3266566)

Utilizator velenos14Iustin Ouatu velenos14 Data 9 ianuarie 2025 15:51:24
Problema Oo Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.52 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <sstream>
#include <stdio.h>
#include <algorithm>

using namespace std;

int main () {

    ifstream f ("oo.in");
    ofstream fout("oo.out");

    int N;
    f >> N;
    // cout << "N = " << N << "\n";

    vector<int> rates (N + 1, 0); // Fortran indexing
    for (int i = 1; i < N + 1; i++) {
        f >> rates[i];
    }

    // Check
    // for (int i = 0; i < N; i++) {
    //     cout << rates[i] << "\n";
    // }

    vector<int> dp (N + 1, 0);
    // Initially using cells 1 and 2 (Fortran indexing)
    // dp(i) = the maximum # of eggs we can collect using the first ``i`` cells 
    // with the hard constraint that we mandatorily use cells 1 and 2 
    dp[0] = 0; // useless
    dp[1] = 0;
    dp[2] = rates[1] + rates[2];
    dp[3] = dp[2];
    dp[4] = dp[3];

    for (int i = 5; i < N; i++) { // the last cell is forbidden to be used because we used cell 1
        dp[i] = max(
                       dp[i - 1], // don't use this cell
                       rates[i] + rates[i - 1] + dp[i - 3] // use this cell  
                    );
    }
    dp[N] = dp[N - 1];

    int max_for_now = *max_element(dp.begin(), dp.end());
    // cout << "max_for_now = " << max_for_now << " and dp[-1] = " << dp.back() << endl;


    // Initially using cells 1 and N
    fill(dp.begin(), dp.end(), 0); // reset
    dp[0] = 0; // useless
    dp[1] = rates[1] + rates[N];
    dp[2] = dp[1]; 
    dp[3] = dp[2];
    for (int i = 4; i < N - 1; i++) { // the last cell has been already used, so cannot touch dp[N - 1]
        dp[i] = max(
                        dp[i - 1],  // don't take it
                        dp[i - 3] + rates[i] + rates[i - 1] // use this cell
                   );
    }
    dp[N - 1] = dp[N - 2];
    dp[N] = dp[N - 1];
    int max_for_now_2 = *max_element(dp.begin(), dp.end());
    // cout << "max_for_now_2 = " << max_for_now_2 << " and dp[-1] = " << dp.back() << endl;


    // Initially using cells 2 and 3
    fill(dp.begin(), dp.end(), 0); // reset
    dp[0] = 0;
    dp[1] = 0;
    dp[2] = 0;
    dp[3] = rates[2] + rates[3];
    dp[4] = dp[3];
    dp[5] = dp[4];
    for (int i = 6; i < N + 1; i++) {
        dp[i] = max(
                      dp[i - 1],
                      dp[i - 3] + rates[i] + rates[i - 1] 
                   );
    }
    int max_for_now_3 = *max_element(dp.begin(), dp.end());
    // cout << "max_for_now_3 = " << max_for_now_3 << " and dp[-1] = " << dp.back() << endl;
    fout << max({max_for_now, max_for_now_2, max_for_now_3}) << "\n";

    return 0;
}