#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef vector <int> vi;
typedef vector <ll> vl;
typedef vector<string> vs;
typedef vector<bool> vb;
typedef vector <char> vc;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vl> vvl;
typedef vector<vc> vvc;
typedef vector<vs> vvs;
typedef pair<ll,ll> pl;
typedef double dou;
typedef vector<pl> vpl;
typedef unsigned long long ull;
typedef uint64_t i64;
typedef vector<ull> vull;
#define f first
#define s second
#define pb push_back
#define sz(x) int((x).size())
#define all(x) begin(x), end(x)
#define ts to_string
#define lb lower_bound
#define ub upper_bound
#define yes cout<<'Y'<<'E'<<'S'<<endl
#define no cout<<'N'<<'O'<<endl
#define nd "\n"
void setIO(string name=""){ios_base::sync_with_stdio(0);cin.tie(0);if(sz(name)){freopen((name+".in").c_str(),"r",stdin);freopen((name+".out").c_str(),"w",stdout);}}
ll gcd(ll a, ll b) {return b == 0 ? a : gcd(b, a % b);}
ll mcm(ll a, ll b) {return (a * b) / gcd(a, b);}
bool prime(ll n) {for(int i=2; i<=sqrt(n); i++) if(n%i==0) return false; return true;}
struct compii{bool operator()(const ii &a, const ii &b){if(a.f==a.s)return a.s<b.s;return a.f>b.f;}};
bool comp(int a, int b) {return a>b;}
ll binpow(ll n, ll x){ll ans=1; while(x){if(x&1){ans*=n;}n*=n; x>>=1;} return ans;}
namespace operators {
template<typename T1, typename T2>istream& operator>>(istream& in, pair<T1, T2>& x){in >> x.first >> x.second;return in;}
template<typename T1, typename T2>ostream& operator<<(ostream& out, pair<T1, T2> x){out << x.first << " " << x.second;return out;}
template<typename T1>istream& operator>>(istream& in, vector<T1>& x) {for (auto& i : x) in >> i;return in;}
template<typename T1>ostream& operator<<(ostream& out, vector<T1>& x) {for (auto& i : x) out << i << " ";return out;}
template<typename T1, typename T2>ostream& operator<<(ostream& out, vector<pair <T1,T2>>& x) {for (auto& i : x) out << i.f << " "<<i.s;return out;}
template<typename T1, typename T2>istream& operator>>(istream& in, vector<pair <T1,T2>>& x) {for (auto& i : x) in >> i.f >>i.s;return in;}
}
using namespace operators;
int dx[]= {1,0,-1,0};
int dy[]= {0,1,0,-1};
const int pmod = 998244353;
const int mod = 1e9+7;
const ll inf=1e18;
ll sum(ll a, ll b){
return (( (a+mod) %mod) + ((b+mod)%mod))%mod;
}
ll multi(ll a, ll b){
return (((a+mod) %mod) * ((b+mod)%mod))%mod;
}
///
struct UF{
ll n;
vector<ll> p, range;
vector< vector<ll>* > val;
UF(ll m){
n = m;
p.assign(n, 0);
range.assign(n, 0);
val.assign(n, NULL);
for(ll i = 0; i < n; i++){
p[i] = i;
}
}
ll find(ll i){
return (p[i] == i)? i : p[i] = find(p[i]);
}
bool isSame(ll i, ll j){
return (find(i) == find(j));
}
void unite(ll i, ll j, vector<ll>* newVal){
if(isSame(i, j)) return;
ll x = find(i), y = find(j);
if(range[x] > range[y]){
p[y] = x;
val[x] = newVal;
return;
}
p[x] = y;
val[y] = newVal;
if(range[x] == range[y]) range[y]++;
}
};
void solve(){
ll n;
cin >> n;
vector<ll> a(n+1, 0);
vector<ll> res(n+1, inf);
vector<pl> com;
ll ans = 0;
ll mx = 0;
for(ll i = 1; i <= n; i++){
cin >> a[i];
mx = max(mx, a[i]);
}
ans = mx*n;
if(n == 1){
cout << a[1] << endl;
return;
}
if(n == 2){
ans = min(ans, 2*a[1] + a[2]);
cout << ans << endl;
return;
}
if(n == 3){
ans = min(ans, 3*a[1] + 2*a[2]+ a[3]);
ans = min(ans, 3*max(a[1], a[2]) + a[3] );
ans = min(ans, 2*a[1] + max(a[2], a[3]) );
cout << ans << endl;
return;
}
ll actual = a[1], counter = 0;
for(ll i = 1; i <= n; i++){
if(a[i] > actual){
com.pb({actual, counter});
actual = a[i];
counter = 1;
}
else{
counter++;
}
}
com.pb({actual, counter});
pl me = com[0];
vector<pl> com_tot;
ll k = com.size();
for(ll i = 1; i < k; i++){
if( com[i].f*me.s <= me.f*(me.s+com[i].s) ){
me.f = com[i].f;
me.s += com[i].s;
}
else{
com_tot.pb(me);
}
}
com_tot.pb(me);
ll llevo = 0;
for(auto v: com_tot){
ans+= v.s*(v.f+llevo);
llevo+= v.f;
}
cout << ans << endl;
}
int main (){
setIO("");
int t=1;
//cin >> t;
while(t-->0) solve();
return 0;
}
Compilation message
Discharging.cpp: In function 'void setIO(std::string)':
Discharging.cpp:34:88: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
34 | void setIO(string name=""){ios_base::sync_with_stdio(0);cin.tie(0);if(sz(name)){freopen((name+".in").c_str(),"r",stdin);freopen((name+".out").c_str(),"w",stdout);}}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Discharging.cpp:34:128: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
34 | void setIO(string name=""){ios_base::sync_with_stdio(0);cin.tie(0);if(sz(name)){freopen((name+".in").c_str(),"r",stdin);freopen((name+".out").c_str(),"w",stdout);}}
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1 ms |
340 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
119 ms |
15976 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
212 KB |
Output is correct |
| 2 |
Incorrect |
1 ms |
212 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
