Cod sursa(job #2923152)
Utilizator | Marcu Mihai marcumihai | Data | 11 septembrie 2022 19:50:32 |
---|---|---|---|
Problema | Euro | Scor | 30 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva de probleme | Marime | 0.56 kb |
#include <bits/stdc++.h>
using namespace std;
ifstream f ("euro.in");
ofstream g ("euro.out");
int n;
long long a[100005];
long long sumpart[100005];
long long dp[100005];
int t;
int main()
{
f>>n>>t;
for(int i=1;i<=n;++i)
f>>a[i];
for(int i=1;i<=n;++i)
sumpart[i]=sumpart[i-1]+a[i];
for(int i=1;i<=n;++i)
dp[i]=LLONG_MIN;
for(int i=1;i<=n;++i)
{
for(int j=0;j<=i;++j)
dp[i]=max(dp[i] , dp[j-1]+1LL*i*(sumpart[i]-sumpart[j-1])-t);
}
g<<dp[n];
return 0;
}