student's blog

By student, history, 3 years ago, In English

I need the solution of this problem: J. Straight

Can anyone help me?

#include <bits/stdc++.h>

using namespace std;

#define x 1e5

int n, m, s;
vector<int> cards;

int tmp[int(x)];


inline void solve()
{
    cin >> n >> m >> s;
    for (int i = 0; i < m; i++) cin >> tmp[i];

    sort(tmp, tmp + m);

    cards.push_back(tmp[0]);
    for (int i = 0; i < m; i++) if (cards.back() != tmp[i]) cards.push_back(tmp[i]);

//    for (int card : cards) cerr << card << ' '; cerr << endl;


    int prev = 0, delta = m - s - 1;
    int result = 0;
    for (int i = 0; i < int(cards.size()) - delta; i++) {
//        cerr << i << ' ' << i + delta << endl;
        int diff = cards[i + delta] - cards[i];
//        cerr << diff << endl;
        if (diff < m) {
            int d = cards[i + delta] - m + 1;
            if (d <= prev) d = prev + 1;

            result += cards[i] - d + 1;
            prev = cards[i];

//            cerr << result << endl;
        }
    }
    cout << result << endl;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    solve();

    return 0;
}

Full text and comments »

  • Vote: I like it
  • +6
  • Vote: I do not like it