結果

問題 No.616 へんなソート
コンテスト
ユーザー uenoku
提出日時 2017-12-16 14:55:57
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,186 bytes
コンパイル時間 2,201 ms
コンパイル使用メモリ 180,036 KB
実行使用メモリ 12,760 KB
最終ジャッジ日時 2024-12-14 19:20:55
合計ジャッジ時間 11,955 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 25 TLE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#define rep(i, n) for (lli i = 0; i < (n); i++)
#define rrep(i, n) for (lli i = (n)-1; i >= 0; i--)
using namespace std;
using lli = long long int;
lli mod = 1e9 + 7;
template <class T>
class segtree
{
public:
    lli n;
    vector<T> dat;
    function<T(T, T)> func;
    T dummy;
    vector<T> lazy;
    segtree<T>(lli _n, T ini, function<T(T, T)> f) : func(f), dummy(ini)
    {
        n = 1;
        while (n < _n) {
            n = n * 2;
        }
        dat.assign(2 * n - 1, ini);
        lazy.assign(2 * n - 1, 0);
    }
    void update(lli k, T a)
    {
        k += n - 1;
        dat[k] = a;
        while (k > 0) {
            k = (k - 1) / 2;
            dat[k] = func(dat[k * 2 + 1], dat[k * 2 + 2]);
        }
    }
    T query(int a, int b)
    {
        return query(a, b, 0, 0, n);
    }
    // [a,b)の何かを求める.
    T query(int a, int b, int k, int l, int r)
    {
        //交差しないときはダミー
        if (r <= a || b <= l)
            return dummy;
        if (a <= l && r <= b)
            return dat[k];
        else {
            T vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
            T vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
            return func(vl, vr);
        }
    }
    T get(int a)
    {
        return query(a, a + 1, 0, 0, n);
    }
};
int main()
{
    int n, k;
    cin >> n >> k;
    vector<lli> a(n);
    rep(i, n) cin >> a[i];
    sort(a.begin(), a.end());
    auto f = [](lli a, lli b) -> lli { return (a + b) % mod; };
    segtree<lli> seg(k + 1, 0, f);
    lli dp[310][310] = {};
    // i 番目まで使ったとき転置数がjであるような場合の数
    // dp[0][0] = 1;
    // dp[1][1] = 1;
    // dp[1][0] = 1;

    seg.update(0, 1);
    rep(i, n)
    {
        segtree<lli> new_seg(k + 1, 0, f);

        rep(j, k + 1)
        {
            if (j > i * (i + 1) / 2)
                continue;
            // dp[i+1][j+i..0] += dp[i][j];
            // dp[i+1][j] = sum(dp[i][j-i]..d[i][j]);
            lli dat = seg.query(max(j - i, 0LL), j + 1);
            new_seg.update(j, dat);
        }
        swap(new_seg, seg);
    }
    cout << seg.query(0, k + 1) << endl;
}
0