## ABA12E Statement

Dhinakaran is very fond of games. Shooting the balloons is his favourite. In this game, there are ‘n’ balloons which are arranged in a line. Every balloon has a unique number which is the number of points earned if that balloon is shot. A constraint here is that you should shoot contiguous balloons. So, Dhinakaran wanted to find the maximum number of points he could earn. He sought help from a friend who told him that it was the famous maximum contiguous sum problem. So Dhinakaran learnt about it and was happy. But Dhinakaran is not someone who gets satisfied so easily. He wanted to find the k-th smallest possible contiguous sum! Now, his friend was not able to solve this. So he came to me. I suggested that he approach you. You are a great coder, aren’t you? Help him out.

There will be atleast 1 balloon and atmost 50000 balloons, and each balloon can have atleast 0 point and atmost 10^{9} points.

### Input

The first line of each data set contains the number of balloons and value of k.

1 <= k <= (n * (n + 1)) / 2

The second line contains N space separated integers.

### Output

The output for each test case should be a single line containing the k-th smallest possible contiguous sum of points that could be achieved.

## ABA12E Solution

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 |
#include <iostream> #include <cstdio> #include <cstdlib> #include <cmath> #include <cstring> #include <numeric> #include <algorithm> #include <functional> #include <vector> #include <queue> #include <stack> #include <set> #include <map> //#include <unordered_map> #include <bitset> #include <utility> #include <cassert> #include <iomanip> #include <ctime> #include <fstream> using namespace std; const int me = 100025; int N; long long K, sum; int a[me]; int main(int argc, const char * argv[]) { ios_base::sync_with_stdio(0); cin.tie(0); cin >> N >> K; for(int i = 1; i <= N; i ++) cin >> a[i]; for(int i = 1; i <= N; i ++) sum = sum + a[i]; if(N == 0){ cout << 0 << endl; return 0; } long long low = 0, high = sum, mid, best = high; while(low <= high){ mid = (low + high) / 2; long long s = 0, current_sum = 0; int ptr = 0; for(int i = 1; i <= N; i ++){ while(ptr < N && current_sum + a[ptr + 1] <= mid){ current_sum += a[++ptr]; } if(ptr >= i) s += ptr - i + 1; current_sum -= a[i]; } if(s >= K){ best = mid; high = mid - 1; } else{ low = mid + 1; } } cout << best << endl; return 0; } |