ALIEN.cpp

#include<iostream>
using namespace std;
 
const int MAX = 100005;
 
int At;            // Số lượng trạm tàu
int Bt;            // Số lượng người tối đa mà người ngoài hành tinh muốn nhìn
int a[MAX];        // Số lượng người tại mỗi trạm
 
int main()
{
    ios::sync_with_stdio(false);
 
    // comment dòng này trước khi submit
    freopen("input.txt","r",stdin);
 
    int T;
    cin >> T;
 
    for(int tc = 0; tc < T; tc++)
    {
        cin >> At >> Bt;
        for(int i = 0; i < At; i++)
            cin >> a[i];
 
        int max_path = 0;            // Đường đi dài nhất
        int min_sum  = Bt + 1;        // Số lượng người ít nhất đã gặp
 
        int i = 0, st = 0;
        int sum = 0;                // Số lượng người đã gặp
 
        while(i < At)
        {
            sum += a[i];
 
            // kiểm tra cho đến khi 
            // tổng số người đã gặp > số lượng mong muốn
            if(sum > Bt)
            {
                // độ dài đường đi hiện tại
                int path = i - st;
 
                // số lượng người đã gặp hiện tại
                int people = sum - a[i];
 
                // Kiểm tra nếu đường đi dài hơn thì cập nhật
                // trường hợp đường đi bằng nhau thì chọn đường
                // có số lượng người gặp ít hơn
                if(path > max_path)
                { 
                    max_path = path;
                    min_sum = people;
                }
                else if(path == max_path)
                {
                    if(people < min_sum) min_sum = people;
                }
 
                // tăng điểm bắt đầu cho đến khi 
                //tổng số người < số lượng mong muốn để duyệt tiếp
                while(sum > Bt)
                {
                    sum -= a[st];
                    st++;
                }    
            }
 
            i++;
        }
 
        // Kiểm tra lần cuối cùng
        int path = i - st;
        if(path > max_path)
        { 
            max_path = path;
            min_sum  = sum;
        }
        else if(path == max_path)
        {
            if(sum < min_sum) min_sum = sum;
        }
 
        cout << min_sum << " "  << max_path << endl;
 
    }
 
    return 0;
}