[Link] https://www.acmicpc.net/problem/1744
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <cstring>
// #include <bits/stdc++.h>
using namespace std;
#define for0(i, n) for(int i = 0; i < n; i++)
#define for1(i, n) for(int i = 1; i < n; i++)
#define fori(s, e) for(int i = s; i < e; i++)
#define ll long long
#define endl "\n"
#define nulls '\0'
#define dkdk " "
const int MAX = 5e5 + 1;
int n;
int main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
// freopen("input.txt", "r", stdin);
cin >> n;
vector<int> nvec;
bool zero_exist = false;
for0(i, n) {
int in; cin >> in;
if(in) nvec.push_back(in);
else zero_exist = true;
}
sort(nvec.begin(), nvec.end());
int lb_zero = upper_bound(nvec.begin(), nvec.end(), 0) - nvec.begin();
int ub_one = upper_bound(nvec.begin() + lb_zero, nvec.end(), 1) - nvec.begin();
int lb_one = lower_bound(nvec.begin() + lb_zero, nvec.end(), 1) - nvec.begin();
int sum = 0, i = nvec.size() - 1;
while(i-1 >= ub_one) {
sum += nvec[i]*nvec[i-1];
i-=2;
}
if(i == ub_one) sum+=nvec[i];
sum+= ub_one - lb_one;
i = 0;
while(i+1<lb_zero) {
sum+=nvec[i]*nvec[i+1];
i+=2;
}
if(i == lb_zero -1 && !zero_exist) sum+=nvec[lb_zero-1];
cout << sum;
return 0;
}