1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

const int MAXN = 1e3 + 3;

int cnt[MAXN];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  int n, k;
  cin >> n >> k;
  FOR(i, 0, n) {
    int x;
    cin >> x;
    ++cnt[x - 1];
  }

  int res = 0, odd = 0;
  FOR(i, 0, k) {
    res += cnt[i] / 2;
    odd += cnt[i] % 2;
  }
  res *= 2;
  res += (odd + 1) / 2;
  // dbg(odd);
  cout << res << "\n";

  return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  int n, k;
  cin >> n >> k;

  double delta = 9.0 / 4 + 2LL * (k + n);
  cout << n - int(-1.5 + sqrt(delta) + 1e-9) << "\n";

  return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

const int MAXN = 1e5 + 3;

int h[2][MAXN];
ll dp[3][MAXN];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  int n;
  cin >> n;

  FOR(i, 0, n) { cin >> h[0][i]; }
  FOR(i, 0, n) { cin >> h[1][i]; }

  dp[0][0] = h[0][0];
  dp[1][0] = h[1][0];
  dp[2][0] = 0;

  FOR(i, 1, n) {
    dp[0][i] = max(dp[1][i - 1], dp[2][i - 1]) + h[0][i];
    dp[1][i] = max(dp[0][i - 1], dp[2][i - 1]) + h[1][i];
    dp[2][i] = max(dp[0][i - 1], dp[1][i - 1]);
    dp[2][i] = max(dp[2][i], dp[2][i - 1]);
  }

  cout << max(max(dp[0][n - 1], dp[1][n - 1]), dp[2][n - 1]) << "\n";

  return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

const int MAXN = 1e5 + 3;
const int MAXL = 11;

string nums[MAXN];
int cnt[MAXL];

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  int n;
  cin >> n;

  FOR(i, 0, n) {
    cin >> nums[i];
    ++cnt[nums[i].length()];
  }

  auto first = [&](string num, int l) {
    int res = 0, n = num.length(), p = 1;

    reverse(ALL(num));

    FOR(i, 0, max(n, l)) {
      if (i < l) {
        p = p * 10LL % MOD;
      }
      if (i < n) {
        res = (res + 1LL * (num[i] - '0') * p) % MOD;
        p = p * 10LL % MOD;
      }
    }
    return res;
  };

  auto second = [&](string num, int l) {
    int res = 0, n = num.length(), p = 1;

    reverse(ALL(num));

    FOR(i, 0, max(n, l)) {
      if (i < n) {
        res = (res + 1LL * (num[i] - '0') * p) % MOD;
        p = p * 10LL % MOD;
      }
      if (i < l) {
        p = p * 10LL % MOD;
      }
    }
    return res;
  };

  int ans = 0;
  FOR(i, 0, n) {
    FOR(j, 0, MAXL) {
      if (cnt[j] == 0) {
        continue;
      }

      int t = first(nums[i], j);
      ans = (ans + 1LL * t * cnt[j]) % MOD;
      t = second(nums[i], j);
      ans = (ans + 1LL * t * cnt[j]) % MOD;
    }
  }

  cout << ans << "\n";
  return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67

const int MAXN = 3e3 + 3;

int h[MAXN][MAXN], mi[MAXN][MAXN];
int que[MAXN], head, tail;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);

  int n, m, a, b, x, y, z, g;
  cin >> n >> m >> a >> b;
  cin >> g >> x >> y >> z;

  FOR2(i, 0, n, j, 0, m) {
    h[i][j] = g;
    g = (1LL * x * g + y) % z;
  }

  FOR(i, 0, n) {
    head = tail = 0;
    FOR(j, 0, b) {
      while (head < tail && h[i][j] <= h[i][que[tail - 1]]) {
        --tail;
      }
      que[tail++] = j;
    }
    mi[i][b - 1] = h[i][que[head]];

    FOR(j, b, m) {
      if (j - que[head] >= b) {
        ++head;
      }
      while (head < tail && h[i][j] <= h[i][que[tail - 1]]) {
        --tail;
      }
      que[tail++] = j;
      mi[i][j] = h[i][que[head]];
    }
  }

  ll ans = 0;
  FOR(j, b - 1, m) {
    head = tail = 0;
    FOR(i, 0, a) {
      while (head < tail && mi[i][j] <= mi[que[tail - 1]][j]) {
        --tail;
      }
      que[tail++] = i;
    }
    ans += mi[que[head]][j];
    FOR(i, a, n) {
      if (i - que[head] >= a) {
        ++head;
      }
      while (head < tail && mi[i][j] <= mi[que[tail - 1]][j]) {
        --tail;
      }
      que[tail++] = i;
      ans += mi[que[head]][j];
    }
  }

  cout << ans << "\n";

  return 0;
}