Submission #1181824

#	Time	Username	Problem	Language	Result	Execution time	Memory
1181824		random_name	Discharging (NOI20_discharging)	C++20	20 / 100	228 ms	8244 KiB

Discharging

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

#define long long long
#pragma region overloadings
template <typename T1, typename T2>
ostream& operator<< (ostream& os, const pair<T1, T2>& pair){
    os << '(' << pair.first << ", " << pair.second << ')';
    return os;
}

template <typename T1, typename T2>
ostream& operator<< (ostream& os, const map<T1, T2>& map_var){
    for(pair<T1, T2> i: map_var){
        os << '(' << i.first << ": " << i.second << ") ";
    }

    return os;
}

template <typename T>
ostream& operator<< (ostream& os, const vector<T>& vec){
    for(T i: vec)
        os << i << ' ';
    return os;
}

template <typename T1, typename T2>
istream& operator>> (istream& is, pair<T1, T2>& pair){
    is >> pair.first >> pair.second;
    return is;
}

template <typename T>
istream& operator>> (istream& is, vector<T>& vec){
    for(int i = 0; i < vec.size(); i++)
        is >> vec[i];

    return is;
}
#pragma endregion

bool test_cases = false;
ifstream ifile;
ofstream ofile;

// #define cin ifile
// #define cout ofile

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

    vector<long> A(n);
    cin >> A;

    // Non decreasing
    long arr_max = 0;

    for(int i = 0; i < n; i++){
        arr_max = max(arr_max, A[i]);
        A[i] = arr_max;
    }

    map<int, int> c_arr;
    for(int i = 0; i < n; i++){
        c_arr[A[i]]++;
    }

    for(int i = n-2; i >= 0; i--){
        long merge = c_arr[A[i]] * (A[i+1] - A[i]);
        long split = (n-i-1) * (A[i]);

        if(merge < split && A[i] != A[i+1] && c_arr[A[i+1]] != 0){
            c_arr[A[i+1]] += c_arr[A[i]];
            c_arr[A[i]] = 0;
        }
    }

    // cout << c_arr;

    long sum = 0;
    long diff_sum = 0;
    for(pair<int, int> i: c_arr){
        sum += (i.first + diff_sum)*i.second;
        if(i.second != 0)  diff_sum += i.first;
    }

    cout << sum;
}

int main(){
    ifile.open("circlecross.in");
    ofile.open("circlecross.out");

    if(test_cases){
        int t;
        cin >> t;
        while(t--){
            solution();
        }
    }

    else{
        solution();
    }
} 

• Subtask 1: 9 / 9
• Subtask 2: 0 / 13
• Subtask 3: 0 / 25
• Subtask 4: 11 / 11
• Subtask 5: 0 / 14
• Subtask 6: 0 / 28