Cod sursa(job #3312982)

Utilizator Razvan8888Popescu Razvan Razvan8888 Data 1 octombrie 2025 15:36:49
Problema Parantezare optima de matrici Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <fstream>

using namespace std;

ifstream in("podm.in");
ofstream out("podm.out");

long long n, v[505];

long long sum;

int main(){
    in>>n;
    n = n + 1;
    for(int i = 1; i <= n; i++)
        in>>v[i];
    int aux = n;
    while(aux > 3){
        long long maxi = -1, indmaxi;
        for(int i = 2; i < n; i++){
            if(v[i] > maxi){
                maxi = v[i];
                indmaxi = i;
            }
        }
        long long t1, t2;
        for(int i = indmaxi + 1; i <= n; i++){
            if(v[i] != 0){
                t2 = v[i];
                break;
            }
        }
        for(int i = indmaxi - 1; i >= 1; i--){
            if(v[i] != 0){
                t1 = v[i];
                break;
            }
        }
        long long pas = t1 * v[indmaxi] * t2;
        sum += pas;
        aux--;
        v[indmaxi] = 0;
    }
    long long t1, t2, t3;
    for(int i = 2; i < n; i++){
        if(v[i] != 0){
            t2 = v[i];
            break;
        }
    }
    t1 = v[1];
    t3 = v[n];
    long long pas = t1 * t2 * t3;
    sum += pas;
    out<<sum;
    return 0;
}