Đề Tài Giải Thuật Hrbust ACM Tuần 5 - Năm Học 2024

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

from itertools import accumulate
input()
min_number = 0
last_number = 0
for n in accumulate(map(int, input().split())):
  if n < min_number:
    min_number = n
  last_number = n
if min_number < 0:
  min_number = -min_number
  print(min_number + last_number)
else:
  print(last_number)

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

from itertools import accumulate

n, m = map(int, input().split())
l = []
for _m in range(n):
  l.append([])
  for _ in range(n + 1):
    l[_m].append(0)
while m > 0:
  m -= 1
  x1, y1, x2, y2 = map(int, input().split())
  for x in range(x1 - 1, x2):
    l[x][y1 - 1] += 1
    l[x][y2] -= 1
for sl in l:
  print(*list(accumulate(sl[:-1])))

 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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int o[5010][5010];
void add(int x, int y, int v) { o[x][y] += v; }
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, r, x, y, v;
  cin >> n >> r;
  int max_x = r, max_y = r;
  for (int i = 0; i < n; i++) {
    cin >> x >> y >> v;
    x++; // Tăng chỉ số x và y để tránh vượt quá giới hạn
    y++;
    if (x > max_x) {
      max_x = x;
    }
    if (y > max_y) {
      max_y = y;
    }
    add(x, y, v);
  }
  for (int _x = 1; _x <= max_x; _x++) {
    for (int _y = 1; _y <= max_y; _y++) {
      o[_x][_y] =
        o[_x][_y] + o[_x - 1][_y] + o[_x][_y - 1] - o[_x - 1][_y - 1];
    }
  }
  int rt = 0;
  for (int _x = r; _x <= max_x; _x++) {
    for (int _y = r; _y <= max_y; _y++) {
      rt = max(rt, o[_x][_y] - o[_x - r][_y] - o[_x][_y - r] +
               o[_x - r][_y - r]);
    }
  }
  cout << rt;
  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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int o[5010][5010];
void add(int x, int y, int v) { o[x][y] += v; }
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int n, r, x, y, v;
  cin >> n >> r;
  int max_x = r, max_y = r;
  for (int i = 0; i < n; i++) {
    cin >> x >> y >> v;
    if (x > max_x) {
      max_x = x;
    }
    if (y > max_y) {
      max_y = y;
    }
    add(x, y, v);
  }
  // Tính tổng tiền tố trên cột y=0
  for (int i = 1; i <= max_x; i++) {
    o[i][0] += o[i - 1][0];
  }
  // Tính tổng tiền tố trên hàng x=0
  for (int j = 1; j <= max_y; j++) {
    o[0][j] += o[0][j - 1];
  }
  // Tính tổng tiền tố từ (1,1)
  for (int _x = 1; _x <= max_x; _x++) {
    for (int _y = 1; _y <= max_y; _y++) {
      o[_x][_y] =
        o[_x][_y] + o[_x - 1][_y] + o[_x][_y - 1] - o[_x - 1][_y - 1];
    }
  }
  int rt = 0;
  // Tính tổng trong ma trận bắt đầu từ (_x-r+1, _y-r+1) đến (_x, _y)
  for (int _x = r - 1; _x <= max_x; _x++) {
    for (int _y = r - 1; _y <= max_y; _y++) {
      int v1, v2, v3, v4;
      v1 = o[_x][_y];
      if (_x - r < 0) {
        v2 = 0;
      } else {
        v2 = o[_x - r][_y];
      }
      if (_y - r < 0) {
        v3 = 0;
      } else {
        v3 = o[_x][_y - r];
      }
      if (_y - r < 0 || _x - r < 0) {
        v4 = 0;
      } else {
        v4 = o[_x - r][_y - r];
      }
      rt = max(rt, v1 - v2 - v3 + v4);
    }
  }
  cout << rt;
  return 0;
}

1

# Trống

1

# Trống

 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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long N = 200000 + 10;
ll scientist_language[N], moive_voice[N], moive_subtitle[N];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll n;
  cin >> n;            // Số lượng nhà khoa học
  map<ll, ll> scientist_language; // Chỉ số ngôn ngữ -> Số nhà khoa học
  for (ll i = 1; i <= n; i++) {
    ll language_index;
    cin >> language_index;
    scientist_language[language_index] += 1;
  }
  ll m;
  cin >> m; // Số lượng phim tại rạp
  for (ll i = 1; i <= m; i++) {
    ll vocie_language;
    cin >> vocie_language;
    moive_voice[i] = vocie_language; // Chỉ số ngôn ngữ giọng nói
  }
  for (ll i = 1; i <= m; i++) {
    ll subtitle_language;
    cin >> subtitle_language;
    moive_subtitle[i] = subtitle_language; // Chỉ số ngôn ngữ phụ đề
  }
  ll very_satisfied = 0;
  ll almost_satisfied = 0;
  ll movie_index = 1; // Giá trị mặc định là 1
  for (ll i = 1; i <= m; i++) {
    ll temp_almost_satisfied = scientist_language[moive_subtitle[i]];
    ll temp_very_satisfied = scientist_language[moive_voice[i]];
    if (temp_very_satisfied > very_satisfied) {
      movie_index = i;
      very_satisfied = temp_very_satisfied;
      almost_satisfied = temp_almost_satisfied;
    } else if (temp_very_satisfied == very_satisfied &&
          temp_almost_satisfied > almost_satisfied) {
      movie_index = i;
      almost_satisfied = temp_almost_satisfied;
    }
  }
  cout << movie_index << endl;
  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

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const long long N = 200000 + 10;
ll scientist_language[N], moive_voice[N], moive_subtitle[N];
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  ll n;
  cin >> n;            // Số lượng nhà khoa học
  map<ll, ll> scientist_language; // Chỉ số ngôn ngữ -> Số nhà khoa học
  for (ll i = 1; i <= n; i++) {
    ll language_index;
    cin >> language_index;
    scientist_language[language_index] += 1;
  }
  ll m;
  cin >> m; // Số lượng phim tại rạp
  for (ll i = 1; i <= m; i++) {
    ll vocie_language;
    cin >> vocie_language;
    moive_voice[i] = vocie_language; // Chỉ số ngôn ngữ giọng nói
  }
  for (ll i = 1; i <= m; i++) {
    ll subtitle_language;
    cin >> subtitle_language;
    moive_subtitle[i] = subtitle_language; // Chỉ số ngôn ngữ phụ đề
  }
  ll very_satisfied = 0;
  ll movie_index = 1; // Giá trị mặc định là 1
  for (ll i = 1; i <= m; i++) {
    ll temp = scientist_language[moive_voice[i]];
    if (temp > very_satisfied) {
      very_satisfied = temp;
      movie_index = i; // Ghi nhận mã phim
    }
  }
  ll almost_satisfied = 0;
  for (ll i = 1; i <= m; i++) {
    ll temp_voice = scientist_language[moive_voice[i]];
    ll temp_subtitle = scientist_language[moive_subtitle[i]];
    if (very_satisfied == temp_voice && almost_satisfied < temp_subtitle) {
      almost_satisfied = temp_subtitle;
      movie_index = i;
    }
  }
  cout << movie_index << endl;
  return 0;
}

1
2
3
4
5
6
7
8
9

from itertools import accumulate
n = int(input())
l = [0] * (1000000 + 2)
while n > 0:
  n -= 1
  a, b = map(int, input().split())
  l[a] += 1
  l[b + 1] -= 1
print(max(accumulate(l)))

 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

from itertools import accumulate

n, q = map(int, input().split())
l = []
for _ in range(0, n + 2):
  l.append(1)
while q > 0:
  q -= 1
  li, ri = map(int, input().split())
  l[li - 1] *= -1
  l[ri] *= -1
_n = 0
last_one = 0
rt = ""
for i in range(0, n):
  if _n == n:
    break
  if l[i] == -1: # Khác phần tử trước đó
    if i == 0 or last_one == 0:
      last_one = 1
    else:
      last_one = 0
    rt += str(last_one)
  else: # Giống phần tử trước đó
    rt += str(last_one)
  _n += 1
print(rt)