Submission #526762

#	Time	Username	Problem	Language	Result	Execution time	Memory
526762		Hydroxic_Acid	Izbori (COCI22_izbori)	C++14	0 / 110	22 ms	1280 KiB

Main

#include <iostream>
#include <cstring>
#include <map>
using namespace std;
#define ll long long

int n;
ll ways = 0;
int arr[200005];
int psum[200005];
int highest = 0;
map<int, int> s;
map<int, int>::iterator it;

int main(){
    cin >> n;
    for(int i = 0; i < n; i++) cin >> arr[i];
    if(arr[0] == 1){
        psum[0] = 1;
        s[psum[0]]++;
    }
    else{
        psum[0] = -1;
        s[psum[0]]++;
    }
    for(int i = 1; i < n; i++){
        if(arr[i] == 1)psum[i] = 1;
        else psum[i] = -1;
        psum[i] += psum[i - 1];
        s[psum[i - 1]]++;
        ways += s[-1 * psum[i]];
    }
    
    cout << (int)((n + 1) * n) / 2 - ways;
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 15
• Subtask 4: 0 / 70