Contest Duration: ~ (local time) (100 minutes) Back to Home

Submission #8039964

Source Code Expand

Copy
```#include <bits/stdc++.h>

using namespace std;

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<int> ls(n);
for (auto& l : ls) {
cin >> l;
}
int max_l = *max_element(ls.begin(), ls.end());
vector<int> count(2*max_l+1, 0);
for (auto l : ls) {
++count[l];
}
vector<int> count_sum(2*max_l+1, 0);
count_sum[0] = count[0];
for (int i = 1; i < (int)count.size(); ++i) {
count_sum[i] = count_sum[i-1] + count[i];
}
// num_1 counts all with a <= b < c
long long num_1 = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (make_pair(ls[i], i) < make_pair(ls[j], j)) {
num_1 += count_sum[ls[i]+ls[j]-1]-count_sum[ls[j]];
}
}
}
// num_2 counts all with a = b = c
long long num_2 = 0;
for (int i = 0; i <= 2*max_l; ++i) {
num_2 += ((long long) count[i])*(count[i]-1)*(count[i]-2)/6;
}
// num_3 counts all with a < b = c
long long num_3 = 0;
for (int i = 0; i <= 2*max_l; ++i) {
long long bc = count[i]*(count[i]-1)/2;
long long a = count_sum[i-1];
num_3 += a*bc;
}
cout << num_1+num_2+num_3 << endl;
return 0;
}
```

#### Submission Info

Submission Time 2019-10-19 21:56:25+0900 D - Triangles Tejs C++14 (GCC 5.4.1) 400 1320 Byte AC 14 ms 256 KB

#### Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample00, sample01, sample02
All 400 / 400 handmade03, handmade04, handmade05, random06, random07, random08, random09, random10, random11, random12, random13, random14, sample00, sample01, sample02
Case Name Status Exec Time Memory