QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#165822 | #5507. Investors | arseny_y# | WA | 4ms | 3508kb | C++23 | 1.7kb | 2023-09-05 22:03:35 | 2023-09-05 22:03:35 |
Judging History
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'