QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #507424 | #5507. Investors | SorahISA | AC ✓ | 3058ms | 566708kb | C++20 | 6.2kb | 2024-08-06 17:31:57 | 2024-08-06 17:31:57 |
Judging History
answer
#ifndef NYCU_MyGO
#define NYCU_MyGO
#include NYCU_MyGO __FILE__ NYCU_MyGO
const int INF = INT_MAX >> 1;
void solve() {
int N, K; cin >> N >> K;
vector<int> A(N);
for (int &x : A) cin >> x;
vector pre(N, vector<int>(N, 0));
vector cost(N, vector<int>(N, 0));
for (int i = 0; i < N; ++i) for (int j = 0; j < N; ++j) {
pre[i][j] = (i < j and A[i] > A[j]) + (i ? pre[i-1][j] : 0) + (j ? pre[i][j-1] : 0) - (i and j ? pre[i-1][j-1] : 0);
}
for (int l = 0; l < N; ++l) for (int r = l; r < N; ++r) {
cost[l][r] = pre[r][r] - (l ? pre[r][l-1] : 0) - (l ? pre[l-1][r] : 0) + (l ? pre[l-1][l-1] : 0);
}
vector dp(2, vector<int>(N, 0));
for (int i = 0; i < N; ++i) dp[0][i] = cost[0][i];
function<void(int, int, int, int, int)> recur = [&](int k, int qL, int qR, int nL, int nR) {
int nM = (nL + nR) >> 1, qM = qL;
dp[k][nM] = dp[k^1][nM];
for (int q = qL; q <= min(nM-1, qR); ++q) {
if (chmin(dp[k][nM], dp[k^1][q] + cost[q+1][nM])) qM = q;
}
if (nL < nM) recur(k, qL, qM, nL, nM-1);
if (nM < nR) recur(k, qM, qR, nM+1, nR);
};
for (int k = 1; k <= K; ++k) recur(k&1, 0, N-1, 0, N-1);
cout << dp[K&1][N-1] << "\n";
}
int32_t main() {
fastIO();
int t = 1; cin >> t;
for (int _ = 1; _ <= t; ++_) {
solve();
}
return 0;
}
#else
#ifdef local
#define _GLIBCXX_DEBUG 1
#endif
#pragma GCC optimize("Ofast", "unroll-loops")
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
#define int i64
using f80 = long double;
#define dobule f80
using pii = pair<int, int>;
template <typename T> using Prior = std::priority_queue<T>;
template <typename T> using prior = std::priority_queue<T, vector<T>, greater<T>>;
#define eb emplace_back
#define ef emplace_front
#define ee emplace
#define pb pop_back
#define pf pop_front
#define ALL(x) begin(x), end(x)
#define RALL(x) rbegin(x), rend(x)
#define SZ(x) ((int)(x).size())
#ifdef local
#define fastIO() void()
#define debug(...) \
fprintf(stderr, "\u001b[33m"), \
fprintf(stderr, "At [%s], line %d: (%s) = ", __FUNCTION__, __LINE__, #__VA_ARGS__), \
_do(__VA_ARGS__), \
fprintf(stderr, "\u001b[0m")
template <typename T> void _do(T &&_t) { cerr << _t << "\n"; }
template <typename T, typename ...U> void _do(T &&_t, U &&..._u) { cerr << _t << ", ", _do(_u...); }
#else
#define fastIO() ios_base::sync_with_stdio(0), cin.tie(0)
#define debug(...) void()
#endif
template <typename T, typename U> bool chmin(T &lhs, U rhs) { return lhs > rhs ? lhs = rhs, 1 : 0; }
template <typename T, typename U> bool chmax(T &lhs, U rhs) { return lhs < rhs ? lhs = rhs, 1 : 0; }
#endif
/**
*
*
*
* iiiiii iiiiiiiiii iiiiiiiiiiiiii
* iiiiiiiiiiiii iiiiiii iiii iiiiiiiiiiiiiii ii iiii
* iiiiiiii iiiiiiiii iiii iiii iii iii iiiiiiiiii
* iiiiiii iiiiii iiii iiii ii iiiiiiiiii iiii iiii
* iiiiii iiiii iiii iiii iii iiii iiiiiiiiiiiiiiiii ii
* iiiiii iiiiiii iiiiiii iiiiiiii iii iiiiiiiiiiiiii iii iiii
* iiiiii iiiiiii iiiii ii iiii iiiiiiiiiii iiii iii iiii iiii iii
* iiiii iiiiiiii ii iiiii iiii iiiiiiiii iii iii iii iii ii iiii
* iiiiii iiiiiiii iiiii iiiii iiiiiiiiiiiiiiii iii iii ii iii iii iiii
* iiiii iiiiii iiii iiiiii iiiiiii iii iii iiii ii i ii iii iii
* iiiiii iiii iiiiiiiiiiiiiii iii iiii iiiii iii ii iii iii ii
* iiiii iiiiiiii iiiiiiiiii iiii iiiiiiiii ii iii ii
* iiiii iiiiii iiii iiiii iii ii ii i
* iiiiii iiiiiiii iiiii iiiii ii ii ii
* iiiii iiii iiii iiiiiiiiiiii ii
* iii iiii iiii iiiiiiii
* iiiii iiii
* iiii iiii
* iiii iiiii
* iii iiiii
* iii iiiii
* iii iiiiii
* iiiiiiiii
* iiiiii
*
*
*
**/
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3616kb
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: 0
Accepted
time: 4ms
memory: 3588kb
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 0 0 0 0 0 1 0 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 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 13 1 0 0 0 ...
result:
ok 349 lines
Test #3:
score: 0
Accepted
time: 41ms
memory: 19532kb
input:
6 1000 333 84886 84887 84732 83775 83776 83777 81234 80288 79661 79243 79244 78520 78521 78522 78523 78524 78525 79041 79042 78509 78120 77073 77432 77433 76111 75362 75363 75364 75365 75366 73979 73980 73981 73982 73983 73984 73472 73473 73075 72948 72949 72727 72728 72383 72384 72272 72273 72274 7...
output:
0 15 683 156 8 242025
result:
ok 6 lines
Test #4:
score: 0
Accepted
time: 897ms
memory: 566460kb
input:
1 6000 1000 35 111 78 14 3 104 13 88 52 138 47 116 208 21 169 90 149 132 146 223 65 193 176 174 175 233 18 164 102 141 163 159 48 85 184 201 215 237 89 139 179 172 68 73 216 80 143 221 61 60 42 207 219 16 43 225 120 44 1 196 157 202 194 137 156 145 27 40 70 217 170 91 77 92 34 54 29 51 140 198 49 18...
output:
847
result:
ok single line: '847'
Test #5:
score: 0
Accepted
time: 2047ms
memory: 566512kb
input:
1 6000 2990 1500 1499 1498 1497 1496 1495 1494 1493 1492 1491 1490 1489 1488 1487 1486 1485 1484 1483 1482 1481 1480 1479 1478 1477 1476 1475 1474 1473 1472 1471 1470 1469 1468 1467 1466 1465 1464 1463 1462 1461 1460 1459 1458 1457 1456 1455 1454 1453 1452 1451 1450 1449 1448 1447 1446 1445 1444 144...
output:
8
result:
ok single line: '8'
Test #6:
score: 0
Accepted
time: 1717ms
memory: 566708kb
input:
1 6000 2442 180 179 178 177 176 175 174 173 172 171 170 169 168 167 166 165 164 163 162 161 160 159 158 157 156 155 154 153 152 151 150 149 148 147 146 145 144 143 142 141 140 139 138 137 136 135 134 133 132 131 130 129 128 127 126 125 124 123 122 121 120 119 118 117 116 115 114 113 112 111 110 109 ...
output:
15
result:
ok single line: '15'
Test #7:
score: 0
Accepted
time: 760ms
memory: 566512kb
input:
1 6000 1100 587239732 341164140 291813224 988290120 53068601 753624625 858461092 949829430 434273763 366369033 221857040 941264717 466308039 367346550 175500843 354302898 380134504 706309233 531982203 378662525 758240314 649219920 350560644 674837065 874382954 509572170 167839902 336312571 979805021...
output:
3556
result:
ok single line: '3556'
Test #8:
score: 0
Accepted
time: 679ms
memory: 566428kb
input:
1 6000 592 5972 5973 5974 5975 5976 5977 5978 5979 5980 5981 5982 5983 5984 5985 5986 5987 5988 5989 5990 5991 5992 5993 5994 5995 5996 5997 5998 5999 6000 5969 5970 5971 5936 5937 5938 5939 5940 5941 5942 5943 5944 5945 5946 5947 5948 5949 5950 5951 5952 5953 5954 5955 5956 5957 5958 5959 5960 5961...
output:
2
result:
ok single line: '2'
Test #9:
score: 0
Accepted
time: 3058ms
memory: 566364kb
input:
1 6000 5998 6000000 5999000 5998000 5997000 5996000 5995000 5994000 5993000 5992000 5991000 5990000 5989000 5988000 5987000 5986000 5985000 5984000 5983000 5982000 5981000 5980000 5979000 5978000 5977000 5976000 5975000 5974000 5973000 5972000 5971000 5970000 5969000 5968000 5967000 5966000 5965000 ...
output:
1
result:
ok single line: '1'