QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#165822#5507. Investorsarseny_y#WA 4ms3508kbC++231.7kb2023-09-05 22:03:352023-09-05 22:03:35

Judging History

你现在查看的是最新测评结果

  • [2023-09-05 22:03:35]
  • 评测
  • 测评结果:WA
  • 用时:4ms
  • 内存:3508kb
  • [2023-09-05 22:03:35]
  • 提交

answer

//I wrote this code 4 u today
#include <bits/stdc++.h>

template<class t> using vc = std::vector<t>;

#define nd node*
#define pnd pair<nd, nd>

using namespace std;
typedef long long ll;
typedef vector<ll> vll;
typedef pair<ll, ll> pll;
typedef vc<pll> vpll;
typedef vc<vll> vvll;
typedef vc<vpll> vvpll;

template<const ll MOD>
struct mod_mul : std::multiplies<const ll> {
    ll operator()(const ll a, const ll b) {
        return (a * b) % MOD;
    }
};


template<typename T>
inline void sort(T &a) {
    sort(a.begin(), a.end());
}

template<typename T>
inline void unique(T &a) {
    a.resize(unique(a.begin(), a.end()) - a.begin());
}

template<typename T>
inline void reverse(T &a) {
    reverse(a.begin(), a.end());
}

const ll INF = 9023372036854775808ll;
const ll MOD = 1000000007ll;

int main() {
    cin.tie(nullptr)->ios_base::sync_with_stdio(false);
    int t;
    cin >> t;
    while (t--) {
        int n, k;
        cin >> n >> k;
        vc<int> a(n);
        for (auto &i: a) cin >> i;
        a.insert(a.begin(), 0);
        vc<vc<int>> dp(n + 2, vc<int>(n + 2, INF));
        vc<vc<int>> cnt(n + 2, vc<int>(n + 2));
        for (int i = 1; i <= n; ++i) for (int j = i, now = 0; j >= 1; --j) {
            cnt[j][i] = cnt[j][i - 1] + (now += (a[i] < a[j]));
        }
        for (int i = 1; i <= n; ++i) dp[i][0] = cnt[1][i];
        for (int i = 0; i <= k; ++i) dp[0][i] = 0;
        for (int i = 2; i <= n; ++i) {
            for (int c = 1; c <= k; ++c) {
                for (int j = 0; j < i; ++j) {
                    dp[i][c] = min(dp[j][c - 1] + cnt[j + 1][i], dp[i][c]);
                }
            }
        }
        cout << dp[n][k] << '\n';
    }
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3436kb

input:

2
6 1
4 5 6 2 2 1
6 2
4 5 6 2 2 1

output:

2
0

result:

ok 2 lines

Test #2:

score: -100
Wrong Answer
time: 4ms
memory: 3508kb

input:

349
6 2
2 1 2 1 2 1
48 12
42 47 39 39 27 25 22 44 45 13 5 48 38 4 37 6 24 10 42 38 12 37 31 19 44 6 29 17 7 12 7 26 35 24 15 9 37 3 27 21 33 29 34 20 14 30 31 21
48 12
1 43 17 46 17 39 40 22 25 2 22 12 4 11 38 12 4 11 1 5 39 44 37 10 19 20 42 45 2 45 37 20 48 34 16 41 23 18 13 44 47 21 29 4 23 18 16...

output:

1
18
15
145
0
2
1
0
13
13
23
0
0
0
1
0
0
0
0
0
0
0
0
161
3
0
0
1
0
1
0
0
0
0
1
1
3
0
0
1
0
0
1
0
0
1
4
0
0
0
0
0
0
0
0
2
0
2
0
0
8
280
0
0
34
4
0
1
0
0
3
0
0
0
0
0
0
0
4
0
0
0
0
0
0
0
0
0
0
0
0
0
3
0
0
0
2
0
0
0
0
0
0
0
8
1
8
0
0
0
0
1
11
5
0
0
0
6
0
1
0
0
0
1
0
0
0
0
0
0
1
0
0
1
0
0
0
0
13
1
0
0
0
...

result:

wrong answer 30th lines differ - expected: '0', found: '1'