// A+B (Your First Submission)
#include
int main() {
// Read input
int a, b;
scanf("%d %d", &a, &b);
// Compute answer
int ans = a + b;
// Print output
printf("%d\n", ans);
}
// Prefix Sum - Motivation
#include
int N, A[100005], pre[100005], Q, l, r;
int main() {
// Read input
scanf("%d", &N);
for (int i = 1; i <= N; i++) scanf("%d", &A[i]);
// Compute prefix sums
for (int i = 1; i <= N; i++) pre[i] = pre[i-1] + A[i];
// Answer queries
scanf("%d", &Q);
for (int i = 1; i <= Q; i++) {
scanf("%d %d", &l, &r);
printf("%d\n", pre[r] - pre[l-1]);
}
}
// Bad Subarrays - O(N^3)
#include
int N, A[100005];
int main() {
// Read input
scanf("%d", &N);
int sum = 0;
int answer = 0;
for (int i = 1; i <= N; i++) scanf("%d", &A[i]);
// Every possible starting point of subarray
for (int i = 1; i <= N; i++) {
// Every possible ending point of subarray
for (int j = i; j <= N; j++) {
sum = 0;
// Add all the elements in the subarray
for (int k = i; k <= j; k++) {
sum += A[k];
}
if (sum == 13) {
answer++;
}
}
}
printf("%d\n",answer);
}
// Bad Subarrays - O(N^2)
#include
int N, A[100005], pre[100005];
int main() {
// Read input
scanf("%d", &N);
int sum = 0;
int answer = 0;
for (int i = 1; i <= N; i++) scanf("%d", &A[i]);
// Compute prefix sums
for (int i = 1; i <= N; i++) pre[i] = pre[i-1] + A[i];
// Every possible starting point of subarray
for (int i = 1; i <= N; i++) {
// Every possible ending point of subarray
for (int j = i; j <= N; j++) {
sum = 0;
// Calculate sum from prefix array, we use i-1 because we want to include A[i]
sum = pre[j] - pre[i-1];
if (sum == 13) {
answer++;
}
}
}
printf("%d\n",answer);
}
// Bad Subarrays - O(N)
// We assume magnitude of any contiguous subarray is <= 50000
// Essentially, instead of using 13 = pre[r] - pre[l-1], we use pre[l-1] = pre[r] - 13
// This is useful because we can store the count of previous prefix sum array values, instead of the value itself
// For example, the prefix sum array [1, 3, 6, 10, 5, 1, 1, 3], we would build the array [0, 3, 0, 2, 0, 1, 1, 0, 0, 0, 1]
// This is because there are 0 zeroes in the array, 3 ones, 0 twos, 2 threes, etc. etc.
// Then if we are looking at an end point i, and we have the previous prefix sum counts up to i, we can just look up pre[i] - 13 and see what the count is
// We use two arrays to store prefix sum counts, one for positive numbers and zero, one for negative numbers
#include
int N, A[100005], pre[100005], prevPosVals[100005], prevNegVals[100005];
int main() {
// Read input
scanf("%d", &N);
int answer = 0;
for (int i = 1; i <= N; i++) scanf("%d", &A[i]);
// Compute prefix sums
for (int i = 1; i <= N; i++) pre[i] = pre[i-1] + A[i];
// Every possible ending point of subarray
for (int i = 1; i <= N; i++) {
// Check how many previous prefix sums we can remove to get 13
if (pre[i]-13 < 0) answer += prevNegVals[-(pre[i]-13)];
else answer += prevPosVals[pre[i]-13];
// Add the current prefix sum to the counts
if (pre[i] < 0) prevNegVals[-pre[i]]++;
else prevPosVals[pre[i]]++;
}
printf("%d\n",answer);
}
// Bad Subarrays - O(N)
// We make no assumptions apart from any contiguous subarray will fit into a C++ int
// This requires use of a map, which will be taught later
// The problem Good Subarrays does not require a map
// http://www.cplusplus.com/reference/map/map/
#include
#include