QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #611296 | #5507. Investors | QHhee004 | TL | 114ms | 38500kb | C++17 | 1.9kb | 2024-10-04 20:14:13 | 2024-10-04 20:14:14 |
Judging History
answer
#include<iostream>
#include<map>
#include<algorithm>
#include<set>
#include<queue>
using namespace std;
const int inf=1e9+7,N=6005;
int n,m;
int tot,a[N],b[N],f[N][N],excel[N][N];
#define lowbit(x) x&-x
class Tree_Array {
private:
int bit[N];
public:
void assign(Tree_Array &t) {
for(int i=1; i<=n; i++)
bit[i]=t.bit[i];
}
void set(int t) {
for(int i=0; i<=n; i++)
bit[i]=t;
}
void add_mn(int x,int t) {
while(x)bit[x]=min(bit[x],t),x-=lowbit(x);
}
int get_mn(int x) {
int ans=inf;
while(x<=n)ans=min(bit[x],ans),x+=lowbit(x);
return ans;
}
void add(int x,int y) {
while(x)bit[x]+=y,x-=lowbit(x);
}
int get(int x) {
int sum=0;
while(x<=n)sum+=bit[x],x+=lowbit(x);
return sum;
}
} bit1,bit2;
void prepare() {
scanf("%d%d",&n,&m);
for(int i=1; i<=n; i++) {
scanf("%d",&a[i]);b[i]=a[i];
}
map<int,int>F;
tot=0;
sort(b+1,b+1+n);
for(int i=1; i<=n; i++)
if(F[b[i]]==0)F[b[i]]=++tot;
for(int i=1; i<=n; i++)a[i]=F[a[i]];
}
void Get_f() {
for(int L=1; L<=n; L++) {
bit1.set(0);
bit1.add(a[L],1);
for(int R=L+1; R<=n; R++) {
f[L][R]=f[L][R-1]+bit1.get(a[R]+1);
bit1.add(a[R],1);
}
}
}
int res[N][N];
void Get_ans() {
bit1.set(inf);
bit2.set(inf);
for(int i=0; i<=n+1; i++)
for(int j=0; j<=n+1; j++)
res[i][j]=inf;
res[0][1]=0;
for(int c=0; c<=m; c++) {
int t=c;
for(int j=1; j<=n; j++) {
res[c+1][j+1]=res[c][t+1]+f[t+1][j];
for(int k=t+1; k<=j; k++) {
if(res[c][k+1]+f[k+1][j]<res[c+1][j+1]) {
t=k;
res[c+1][j+1]=min(res[c+1][j+1],res[c][t+1]+f[t+1][j]);
// break;
}
}
}
}
printf("%d\n",res[m+1][n+1]);
}
void solve() {
prepare();
Get_f();
Get_ans();
}
int main() {
// freopen("data.in","r",stdin);
// freopen("my.out","w",stdout);
int T;scanf("%d",&T);
while(T--) solve();
// fclose(stdin);
// fclose(stdout);
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5884kb
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: 2ms
memory: 8124kb
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: 114ms
memory: 38500kb
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: -100
Time Limit Exceeded
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...