Taulukko

input/code.cpp: In function 'ul countDynamic(std::vector<long unsigned int>*, int, int)':
input/code.cpp:36:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (ul j = 0; j < size; j++) {
                    ~~^~~~~~
input/code.cpp:41:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (countNonZero(&items) <= k) {
         ~~~~~~~~~~~~~~~~~~~~~^~~~
input/code.cpp:47:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         if (countNonZero(&items) <= k) {
             ~~~~~~~~~~~~~~~~~~~~~^~~~
input/code.cpp: In function 'int main(int, const char**)':
input/code.cpp:69:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int m = k + 1; m < list.size() + 1; m++) {
                         ~~^~~~~~~~~~~~~~~~~

#include <iostream>
#include <vector>

using namespace std;

typedef vector <unsigned long> lVect;
typedef unsigned long ul;

ul countNonZero(vector <lVect>* items) {
    ul n = 0;
    for (ul i = 0; i < (*items).size(); i++) {
        if ((*items)[i][1] != 0) {
            n += 1;
        }
    }
    return n;
}

ul maxValue(vector <ul>* seq) {
    ul maxFound = 0;
    for (ul i = 0; i < (*seq).size(); i++) {
        if ((*seq)[i] > maxFound) {
            maxFound = (*seq)[i];
        }
    }
    return maxFound;
}

ul countDynamic(vector <ul>* seq, int size, int k) {
    ul validSublists = 0;
    vector <lVect> items(maxValue(seq) + 1);
    for (ul i = 0; i < items.size(); i++) {
        vector <ul> c = {i, 0};
        items[i] = c;
    }
    for (ul j = 0; j < size; j++) {
        ul index = (*seq)[j];
        // cout << "seq[j]: " << index << endl;
        items[index][1] += 1;
    }
    if (countNonZero(&items) <= k) {
        validSublists += 1;
    }
    for (ul q = size; q < (*seq).size(); q++) {
        items[(*seq)[q]][1] += 1;
        items[(*seq)[q - size]][1] -= 1;
        if (countNonZero(&items) <= k) {
            validSublists += 1;
        }
    }
    return validSublists;
}

int main(int argc, const char * argv[]) {
    int arrayLength;
    int k;
    cin >> arrayLength;
    cin >> k;
    vector <ul> list(arrayLength);
    for (int i = 0; i < arrayLength; i++) {
        int next;
        cin >> next;
        list[i] = next;
    }
    ul sum = 0;
    for (int n = 1; n < k + 1; n++) {
        sum += list.size() - n + 1;
    }
    for (int m = k + 1; m < list.size() + 1; m++) {
        sum += countDynamic(&list, m, k);
    }
    cout << sum;
    return 0;
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 1

Verdict: ACCEPTED

Test 7

Group: 1

Verdict: ACCEPTED

Test 8

Group: 1

Verdict: ACCEPTED

Test 9

Group: 1

Verdict: ACCEPTED

Test 10

Group: 1

Verdict: ACCEPTED

Test 11

Group: 1

Verdict: ACCEPTED

Test 12

Group: 1

Verdict: ACCEPTED

Test 13

Group: 1

Verdict: ACCEPTED

Test 14

Group: 1

Verdict: ACCEPTED

Test 15

Group: 2

Verdict: ACCEPTED

Test 16

Group: 2

Verdict: ACCEPTED

Test 17

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 18

Group: 2

Verdict: ACCEPTED

Test 19

Group: 2

Verdict: ACCEPTED

Test 20

Group: 2

Verdict: ACCEPTED

Test 21

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 22

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 23

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 24

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 25

Group: 2

Verdict: ACCEPTED

Test 26

Group: 2

Verdict: ACCEPTED

Test 27

Group: 2

Verdict: ACCEPTED

Test 28

Group: 2

Verdict: ACCEPTED

Test 29

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 30

Group: 3

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 31

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 32

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 33

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 34

Group: 3

Verdict: TIME LIMIT EXCEEDED

Test 35

Group: 3

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 36

Group: 3

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 37

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 38

Group: 4

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 39

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 40

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 41

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 42

Group: 4

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 43

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 44

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 45

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 46

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 47

Group: 4

Verdict: TIME LIMIT EXCEEDED

Test 48

Group: 4

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 49

Group: 4

Verdict: ACCEPTED

Test 50

Group: 4

Verdict: RUNTIME ERROR

terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc

Test 51

Group: 4

Verdict: ACCEPTED

Test 52

Group: 4

Verdict: ACCEPTED