Submission #61505649

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <string>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <iomanip>
#include <cassert>
#include <cstring>
#include <sstream>
#include <numeric>
#include <cstdio>
#include <bitset>
#include <chrono>
#include <random>
#include <complex>
#include <cmath>
#define F first
#define S second
#define x first
#define y second
#define pii pair<int, int>
#define pll pair<long long, long long>
#define pb push_back
#define ll long long 
#define div divv
#define real() x
#define imag() y 

using namespace std;

typedef long double ld;
typedef long double DOUBLE;
typedef vector<DOUBLE> VD;
typedef vector<VD> VVD;
typedef vector<int> VI;
typedef complex<double> point;

const int N = 200 * 1000 + 10, K = 64, SQ = 650, mod = 998244353;
const ll inf = 1e18;

ll a[N], b[N], c[N];

void solve()
{
	memset(b, 63, sizeof b); memset(c, 63, sizeof c);
	int n; cin >> n;
	for(int i = 0; i < n; i++) cin >> a[i];
	for(int i = 1; i < n; i += 2) b[i / 2] = a[i] - a[i - 1];
	for(int i = 2; i < n; i += 2) c[i / 2 - 1] = a[i] - a[i - 1];
	sort(b, b + n); sort(c, c + n);
	ll ans = a[0] * n;
	for(int i = 1; i < n; i += 2) ans += (n - i) * b[i / 2];
	for(int i = 2; i < n; i += 2) ans += (n - i) * c[i / 2 - 1];
	cout << ans << '\n';
}

int main()
{
	ios::sync_with_stdio(0);
	int t; t = 1; // cin >> t;
	while(t--) solve();
}

Submission Info

Judge Result