From 418399fef4556f890e965adb7b1e483fefbb4f0e Mon Sep 17 00:00:00 2001 From: omagdy7 Date: Mon, 15 Apr 2024 17:19:02 +0200 Subject: Solved 2 problems on codeforces --- codeforces/MaximumSum/main.cpp | 98 +++++++++++++++++++++++++++++ codeforces/MaximumSum/main_input0.txt | 25 ++++++++ codeforces/MaximumSum/main_output0.txt | 12 ++++ codeforces/MedianOfAnArray/main.cpp | 73 +++++++++++++++++++++ codeforces/MedianOfAnArray/main_input0.txt | 17 +++++ codeforces/MedianOfAnArray/main_output0.txt | 8 +++ 6 files changed, 233 insertions(+) create mode 100755 codeforces/MaximumSum/main.cpp create mode 100644 codeforces/MaximumSum/main_input0.txt create mode 100644 codeforces/MaximumSum/main_output0.txt create mode 100755 codeforces/MedianOfAnArray/main.cpp create mode 100644 codeforces/MedianOfAnArray/main_input0.txt create mode 100644 codeforces/MedianOfAnArray/main_output0.txt (limited to 'codeforces') diff --git a/codeforces/MaximumSum/main.cpp b/codeforces/MaximumSum/main.cpp new file mode 100755 index 0000000..bda71e0 --- /dev/null +++ b/codeforces/MaximumSum/main.cpp @@ -0,0 +1,98 @@ +#include +#include + +using namespace std; + +using ll = long long; +using pii = pair; +using vpii = vector; +using vi = vector; +using vll = vector; +using mpii = map; +using mpll = map; +using db = long double; + +#define pb push_back +#define all(x) (x).begin(), (x).end() +#define rall(x) (x).rbegin(), (x).rend() +#define lb lower_bound +#define ub upper_bound +#define make_unique(x) \ + sort(all((x))); \ + (x).resize(unique(all((x))) - (x).begin()) +#define ceil(a, b) ((a) + (b)-1) / (b) + +const int mod = (int)1e9 + 7; +const db pi = acos((db)-1); +const int dx[4]{1, 0, -1, 0}; +const int dy[4]{0, 1, 0, -1}; + +#ifdef LOCAL +#include "debug.h" +#else +#define dbg(...) 42 +#endif + +/* stuff you should look for: + --------------------------- + * special cases (n=1?) + * int overflow, array bounds + * do smth instead of nothing and stay organized + * WRITE STUFF DOWN + * DON'T GET STUCK ON ONE APPROACH + */ + +ll findMaxSubarray(const vector &nums) { + if (nums.empty() || all_of(all(nums), [](int x) { return x < 0; })) + return 0; + + ll maxSum = nums[0]; + ll currentSum = nums[0]; + + for (int i = 1; i < nums.size(); i++) { + if (currentSum < 0) { + currentSum = nums[i]; + } else { + currentSum += nums[i]; + } + + if (currentSum > maxSum) { + maxSum = currentSum; + } + } + + return maxSum; +} + +void solve() { + int n, k; + cin >> n >> k; + vi v(n); + ll sum = 0; + for (auto &x : v) { + cin >> x; + sum += x; + } + ll maxSum = findMaxSubarray(v); + ll res = 2; + for (int i = 1; i < k; i++) { + res = (2 * res) % mod; + } + res = ((res % mod) * (maxSum % mod) - maxSum) % mod; + sum += res; + if (sum % mod < 0) { + cout << sum % mod + mod << '\n'; + } else { + cout << sum % mod << '\n'; + } +} + +int main() { + ios_base::sync_with_stdio(false); + cin.tie(NULL); + int tt; + cin >> tt; + while (tt--) { + solve(); + } +} diff --git a/codeforces/MaximumSum/main_input0.txt b/codeforces/MaximumSum/main_input0.txt new file mode 100644 index 0000000..702f38b --- /dev/null +++ b/codeforces/MaximumSum/main_input0.txt @@ -0,0 +1,25 @@ +12 +2 2 +-4 -7 +3 3 +2 2 8 +1 7 +7 +5 1 +4 -2 8 -12 9 +7 4 +8 14 -9 6 0 -1 3 +7 100 +5 3 -8 12 -5 -9 3 +6 1000 +-1000000000 -1000000000 -1000000000 -1000000000 -1000000000 -1000000000 +2 1 +1000000000 8 +5 4 +0 0 0 0 0 +6 10 +48973 757292 58277 -38574 27475 999984 +7 1 +-1000 1000 -1000 1000 -1000 1000 -1000 +10 10050 +408293874 -3498597 7374783 295774930 -48574034 26623784 498754833 -294875830 283045804 85938045 diff --git a/codeforces/MaximumSum/main_output0.txt b/codeforces/MaximumSum/main_output0.txt new file mode 100644 index 0000000..c3d3d1b --- /dev/null +++ b/codeforces/MaximumSum/main_output0.txt @@ -0,0 +1,12 @@ +999999996 +96 +896 +17 +351 +716455332 +42 +2 +0 +897909241 +0 +416571966 diff --git a/codeforces/MedianOfAnArray/main.cpp b/codeforces/MedianOfAnArray/main.cpp new file mode 100755 index 0000000..c7e8a47 --- /dev/null +++ b/codeforces/MedianOfAnArray/main.cpp @@ -0,0 +1,73 @@ +#include + +using namespace std; + +using ll = long long; +using pii = pair; +using vpii = vector; +using vi = vector; +using vll = vector; +using mpii = map; +using mpll = map; +using db = long double; + +#define pb push_back +#define all(x) (x).begin(), (x).end() +#define rall(x) (x).rbegin(), (x).rend() +#define lb lower_bound +#define ub upper_bound +#define make_unique(x) \ + sort(all((x))); \ + (x).resize(unique(all((x))) - (x).begin()) +#define ceil(a, b) ((a) + (b)-1) / (b) + +const int mod = (int)1e9 + 7; +const db pi = acos((db)-1); +const int dx[4]{1, 0, -1, 0}; +const int dy[4]{0, 1, 0, -1}; + +#ifdef LOCAL +#include "debug.h" +#else +#define dbg(...) 42 +#endif + +/* stuff you should look for: + --------------------------- + * special cases (n=1?) + * int overflow, array bounds + * do smth instead of nothing and stay organized + * WRITE STUFF DOWN + * DON'T GET STUCK ON ONE APPROACH + */ + +void solve() { + int n; + cin >> n; + vi v(n); + for (auto &x : v) { + cin >> x; + } + sort(all(v)); + int m = ceil(n, 2); + int cnt = 1; + for (int i = m - 1; i < n - 1; i++) { + if (v[i] + 1 > v[i + 1]) { + cnt++; + v[i]++; + } else { + break; + } + } + cout << cnt << '\n'; +} + +int main() { + ios_base::sync_with_stdio(false); + cin.tie(NULL); + int tt; + cin >> tt; + while (tt--) { + solve(); + } +} diff --git a/codeforces/MedianOfAnArray/main_input0.txt b/codeforces/MedianOfAnArray/main_input0.txt new file mode 100644 index 0000000..0b3e47b --- /dev/null +++ b/codeforces/MedianOfAnArray/main_input0.txt @@ -0,0 +1,17 @@ +8 +3 +2 2 8 +4 +7 3 3 1 +1 +1000000000 +5 +5 5 5 4 5 +6 +2 1 2 3 1 4 +2 +1 2 +2 +1 1 +4 +5 5 5 5 diff --git a/codeforces/MedianOfAnArray/main_output0.txt b/codeforces/MedianOfAnArray/main_output0.txt new file mode 100644 index 0000000..5054862 --- /dev/null +++ b/codeforces/MedianOfAnArray/main_output0.txt @@ -0,0 +1,8 @@ +1 +2 +1 +3 +2 +1 +2 +3 -- cgit v1.2.3