Cod sursa(job #1895849)

Utilizator teosmTeo SM teosm Data 28 februarie 2017 11:28:29
Problema Oo Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.85 kb
#include <bits/stdc++.h>

using namespace std;

int n, maxim;
vector <int> v, dp;

void read() {
    ifstream fin("oo.in");

    fin >> n;
    v.resize(n + 2); dp.resize(n + 2);
    for (int i = 1; i <= n; ++i) {
        fin >> v[i];
    }

    fin.close();
}

void update_maxim(int start_pos, int end_pos) {
    dp[start_pos] = 0;
    dp[start_pos + 1] = v[start_pos] + v[start_pos + 1];
    for (int i = start_pos + 2; i <= end_pos; ++i) {
        dp[i] = max(dp[i - 1], dp[i - 3] + v[i - 1] + v[i]);
    }

    maxim = max(maxim, dp[end_pos]);
}

void solve() {
    v[n + 1] = v[1];
    update_maxim(1, n - 1);
    update_maxim(2, n);
    update_maxim(3, n + 1);
}

void write() {
    ofstream fout("oo.out");

    fout << maxim;

    fout.close();
}

int main() {
    read();
    solve();
    write();
    return 0;
}