LightOJ 1082 - Array Queries solution in c++

Problem link: 1082 - Array Queries

N.B: This is a segment tree problem. If you do not know about segment tree, spend some time to learn it and please try at least 1 hour to solve it yourself before seeing other's solution. Happy coding! 

1. #include <bits/stdc++.h>
2. using namespace std;
3. #define MAX 200005
4.  
5. int a[MAX];
6. int tree[MAX * 3];
7. void init(int node, int b, int e)
8. {
9.     if (b == e) {
10.         tree[node] = a[b];
11.         return;
12.     }
13.     int left = node * 2;
14.     int right = node * 2 + 1;
15.     int mid = (b + e) / 2;
16.     init(left, b, mid);
17.     init(right, mid + 1, e);
18.     tree[node] = min(tree[left], tree[right]);
19. }
20. int query(int node, int b, int e, int i, int j)
21. {
22.     int x, y;
23.     if (i > e || j < b)
24.         return INT_MAX;
25.     if (b >= i && e <= j)
26.         return tree[node];
27.     int Left = node * 2;
28.     int Right = node * 2 + 1;
29.     int mid = (b + e) / 2;
30.     x = query(Left, b, mid, i, j);
31.     y = query(Right, mid + 1, e, i, j);
32.     return min(x, y);
33. }
34. int main() {
35.     int t;
36.     cin >> t;
37.     for (int tc = 1; tc <= t; tc++)
38.     {
39.         int n, q;
40.         scanf("%d%d", &n, &q);
41.         for (int b = 1; b <= n; b++)
42.             scanf("%d", &a[b]);
43.  
44.         init(1, 1, n);
45.         printf("Case %d:\n", tc);
46.         for (int b = 1; b <= q; b++)
47.         {
48.             int i, j;
49.             scanf("%d%d", &i, &j);
50.             printf("%d\n", query(1, 1, n, i, j));
51.         }
52.     }
53.     return 0;
54. }

LightOJ 1004 - Monkey Banana Problem solution in C++

Problem link: 1004 - Monkey Banana Problem

N.B: This is an iterative DP solution. Please try at least 1 hour yourself before seeing other's solution. Happy coding!  

1. #include <bits/stdc++.h>
2. using namespace std;
3. int main() {
4.    int cs;
5.    cin >> cs;
6.    for(int t = 1; t <= cs; t++) {
7.       int n;
8.       cin >> n;
9.       long long int arr[205][105] = {0}, sum[205][105] = {0};
10.       for(int i = 1; i <= n; i++) {
11.          for(int j = 1; j <= i; j++)
12.             cin >> arr[i][j];
13.       }
14.       int r = n;
15.       for(int i = n + 1; i <= 2 * n - 1; i++) {
16.          for(int j = 1; j <= r - 1; j++)
17.             cin >> arr[i][j];
18.          r--;
19.       }
20.       sum[1][1] = arr[1][1];
21.       for(int i = 2; i <= n; i++) {
22.          for(int j = 1; j <= i; j++) {
23.             if(j == 1) sum[i][j] = sum[i - 1][j] + arr[i][j];
24.             if(j == i) sum[i][j] = sum[i - 1][j - 1] + arr[i][j];
25.             else sum[i][j] = max(sum[i - 1][j - 1], sum[i - 1][j]) + arr[i][j];
26.          }
27.       }
28.       int s = n;
29.       for(int i = n + 1; i <= 2 * n - 1; i++) {
30.          for(int j = 1; j <= s - 1; j++)
31.             sum[i][j] = max(sum[i - 1][j], sum[i - 1][j + 1]) + arr[i][j];
32.          s--;
33.       }
34.       cout << "Case " << t << ": " << sum[2 * n - 1][1] << endl;
35.    }
36.    return 0;
37. }
38.