Cho N dãy số không giảm A1, A2, …, AN, mỗi dãy gồm L số nguyên (dãy số được gọi là không giảm nếu mỗi phần tử đứng sau là lớn hơn hoặc bằng phần tử đứng trước). Xét hai dãy Ai và Aj (1≤ i, j ≤ N), ta gọi dãy gộp (ký hiệu là Aij) của hai dãy Ai, Aj là dãy gồm tất cả 2L phần tử của hai dãy Ai, Aj được sắp xếp theo thứ tự không giảm và phần tử đứng ở vị trí thứ L trong dãy gộp được gọi là phần tử trung vị của nó.
Ví dụ: Xét hai dãy số
Ai = (1 3 4 5 6); Aj = (0 1 5 6 7).
Khi đó dãy gộp Aij từ hai dãy đã cho là
0 1 1 3 4 5 5 6 6 7
có phần tử trung vị là 4.
Yêu cầu: Tính tổng của tất cả các phần tử trung vị của tất cả các dãy gộp Aij với 1≤ i < j ≤ N.
#include <bits/stdc++.h>
using namespace std;
ifstream fi ("TV.INP");
ofstream fo ("TV.OUT");
int main()
{
int n,l;
fi >> n >> l;
long long arr [n+1][l+1];
for(int i=1; i<=n; i++)
{
for(int j=1; j<=l; j++)
{
fi >> arr[i][j];
}
}
long long sum = 0;
for(int i=1; i<n; i++)
{
for(int j=i+1; j<=n; j++)
{
int ai,aj;
ai = aj = 0;
while(true)
{
int temp;
if(arr[i][ai+1] < arr[j][aj+1])
{
ai ++;
temp = arr[i][ai];
}
else
{
aj ++;
temp = arr[j][aj];
}
if(ai + aj == l)
{
sum += temp;
break;
}
}
}
}
fo << sum;
return 0;
}
Đây là code của mình. Nhưng mà nó không chạy được hết ràng buộc: n<=200 và 1<=L<=20000
Run code + Demo Test: https://ideone.com/qEZ6Gc
Test với n = 200 và L=20000: https://secufiles.com/r9A3/Test.txt
Cho mình hỏi là phải tối ưu hóa thế nào để đáp ứng yêu cầu ?