D

//这道题，看假题了网格dp，注意shit的代价公式可以用于每一行的单独计算，此外这个shit是单独作用于每行，和行间无关
//预处理出发点，其次采用刷表法（目前只会超时版本）
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const ll INF = 1e18;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    int t;
    cin >> t;

    while(t--){
        int n, m;
        ll k;
        cin >> n >> m >> k;

        vector<vector<ll>> a(n, vector<ll>(m));
        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++) cin >> a[i][j];
        }


        vector<vector<vector<ll>>> dp(n, vector<vector<ll>>(m, vector<ll>(m, INF)));

        for(int s=0; s<m; s++){
            dp[0][0][s] = s * k + a[0][(0 + s) % m];
        }


        for(int i=0; i<n; i++){
            for(int j=0; j<m; j++){
                for(int s=0; s<m; s++){
                    if(dp[i][j][s] == INF) continue;

                    if(j + 1 < m){

                        ll next_val = a[i][(j + 1 + s) % m];
                        dp[i][j+1][s] = min(dp[i][j+1][s], dp[i][j][s] + next_val);
                    }


                    if(i + 1 < n){
                        for(int s_next=0; s_next<m; s_next++){
                            ll cost = dp[i][j][s] + s_next * k + a[i+1][(j + s_next) % m];
                            dp[i+1][j][s_next] = min(dp[i+1][j][s_next], cost);
                        }
                    }
                }
            }
        }

        ll ans = INF;
        for(int s=0; s<m; s++) ans = min(ans, dp[n-1][m-1][s]);

        cout << ans << "\n";
    }
}

E

//区间覆盖+
//以下是正确代码
// Problem: E. Best Price
// Contest: Codeforces - Codeforces Round 995 (Div. 3)
// URL: https://codeforces.com/contest/2051/problem/E
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef long long ll;
typedef pair<ll,ll> pii;
int get_(vector<ll> &alls,ll v){
    return lower_bound(alls.begin(),alls.end(),v)-alls.begin();
}
void solve(){
    int n,k;
    cin>>n>>k;
    vector<pii> edge(n);
    vector<ll> alls;
    for(int i=0;i<n;i++){
        cin>>edge[i].x;
        alls.emplace_back(edge[i].x);
        //alls.emplace_back(edge[i].y);
    }
    for(int i=0;i<n;i++){
        cin>>edge[i].y;
        alls.emplace_back(edge[i].y+1);
        alls.emplace_back(edge[i].y);
    }
    sort(alls.begin(),alls.end());
    alls.erase(unique(alls.begin(),alls.end()),alls.end());

    vector<int> ok(alls.size()+1),no(alls.size()+1);

    for(int i=0;i<n;i++){
        no[get_(alls,edge[i].x)+1]++;no[get_(alls,edge[i].y)+1]--;
        ok[get_(alls,edge[i].y)]++;
    }
    for(int i=1;i<alls.size();i++){
        no[i]+=no[i-1];
    }
    for(int i=alls.size()-2;i>=0;i--){
        ok[i]+=ok[i+1];
    }

    ll mmax=0;
    for(int i=0;i<alls.size();i++){
        if(no[i]<=k) mmax=max(mmax,ok[i]*alls[i]);
    }

    cout<<mmax<<"\n";

}
int main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }

}
//以下是错误代码，原因是ok的人数和价格是两个变量
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve(){
    int n, k;
    cin >> n >> k;
    vector<pair<ll, ll>> edge(n);
    vector<ll> alls;
    for(int i = 0; i < n; i++) cin >> edge[i].first, alls.emplace_back(edge[i].first);
    for(int i = 0; i < n; i++) cin >> edge[i].second, alls.emplace_back(edge[i].second);

    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());

    ll mmax = 0;
    int l = 0, r = alls.size() - 1;
    while(l <= r){
        int mid = l + (r - l) / 2;
        ll price = alls[mid];
        ll ok = 0, no = 0;//这两个变量无法达到最优解
        for(int i = 0; i < n; i++){
            if(price <= edge[i].first){
                ok++;
            }
            else if(price <= edge[i].second){
                no++;
                ok++;
            }
        }
        if(no <= k){
            mmax = max(mmax, price * ok);
            l = mid + 1;
        }
        else{
            r = mid - 1;
        }
    }
    cout << mmax << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        solve();
    }
}
//所以不应该直接使用二分，但是可以保留枚举，暴力枚举在以下（超时），而且又可以进行前缀和优化，第一个代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve(){
    int n, k;
    cin >> n >> k;
    vector<pair<ll, ll>> edge(n);
    vector<ll> alls;

    for(int i = 0; i < n; i++) {
        cin >> edge[i].first;
        alls.emplace_back(edge[i].first);
    }

    for(int i = 0; i < n; i++) {
        cin >> edge[i].second;
        alls.emplace_back(edge[i].second);
    }

    sort(alls.begin(), alls.end());
    alls.erase(unique(alls.begin(), alls.end()), alls.end());

    ll mmax = 0;

    for(auto price : alls){
        ll ok = 0, no = 0;
        for(int i = 0; i < n; i++){
            if(price <= edge[i].first){
                ok++;
            }
            else if(price <= edge[i].second){
                no++;
                ok++;
            }
        }
        if(no <= k){
            mmax = max(mmax, price * ok);
        }
    }

    cout << mmax << "\n";
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--){
        solve();
    }
}

D

//x<=s-i-j<=y
//把i和s-i-x,s-i-y放进去，然后对每个数字经行二分。有（重复-本身）/2
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int find(vector<ll> &alls,ll tag){
    return lower_bound(alls.begin(),alls.end(),tag)-alls.begin();
}
void solve(){
    ll n,x,y;
    cin>>n>>x>>y;
    vector<ll> vc(n);
    ll sum=0;
    for(int i=0;i<n;i++) {cin>>vc[i];sum+=vc[i];}
    vector<ll> alls;
    alls.push_back(-1e18);//哨兵
    for(int i=0;i<n;i++){
        alls.push_back(vc[i]);//供原查询
        alls.push_back(sum-x-vc[i]);//提供占位贡献
        alls.push_back(sum-y-vc[i]);//
    }
    sort(alls.begin(),alls.end());
    //alls.erase(unique(alls.begin(),alls.end()),alls.end());
    ll res=0;
    ll ans=0;
    vector<ll> b((int)alls.size()+1);
    for(int i=0;i<n;i++){
        b[find(alls,vc[i])]++;//供原查询
    }
    for(int i=1;i<(int)alls.size();i++){
        b[i]+=b[i-1];
    }
    //类似于构造 a1 a2 （a3 【a4） a5】 a6 a7;然后数字间插入了边框
    //然后这个前缀和规避了边框的排名影响
    for(int i=0;i<n;i++){
        ll l=sum-x-vc[i];
        ll r=sum-y-vc[i];
        res+=b[find(alls,l)]-b[find(alls,r)-1];
        if (sum - vc[i] - vc[i] >= x && sum - vc[i] - vc[i] <= y) ans ++;
    }
    cout<<(res-ans)/2<<"\n";

}
int main(){
    ll t;
    cin>>t;
    while(t--){
        solve();
    }
}