Submission #1190868

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190868		vusal	Mountains (NOI20_mountains)	C++20	13 / 100	111 ms	7496 KiB

Mountains

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int oo = 1e18;
const int MAXN = 1e5 + 7;
const int MAXH = 1e2 + 4;

void _()
{
    int n;
    cin >> n;

    vector<int>v(n);
    for(int &i : v) cin >> i;

    vector<int>left(n), right(n);
    vector<int>freq(MAXH, 0);

    for(int i = 0; i < n; i++)
    {
        int h = v[i];
        int cnt = 0;
        for(int j = 0; j < h; j++) cnt += freq[j];
        left[i] = cnt;
        freq[h]++;
    }

    for(int i = 0; i < MAXH; i++) freq[i] = 0;

    for(int i = n - 1; i >= 0; i--)
    {
        int h = v[i];
        int cnt = 0;
        for(int j = 0; j < h; j++) cnt += freq[j];
        right[i] = cnt;
        freq[h]++;
    }

    int sum = 0;

    for(int i = 0; i < n; i++)
    {
        sum += (1LL * left[i] * right[i]);
    }

    cout << sum << endl;
}   

signed main()
{
    int tt = 1;
    // cin >> tt;
    while(tt--) _();
}

• Subtask 1: 0 / 2
• Subtask 2: 4 / 4
• Subtask 3: 9 / 9
• Subtask 4: 0 / 36
• Subtask 5: 0 / 28
• Subtask 6: 0 / 9
• Subtask 7: 0 / 12