- 1#include
- 2#include
- 3#include
- 4#include
- 5#include 6
- 7 using std::fabs;
- 8
- 9typedeflong double lng;
- 10
- 11 const intmxn =505;
- 12 constlng eps = 1E-5;
- 13
- 14 int n, m;
- 15
- 16 struct data
- 17 {
- 18 int c;
- 19 lng s[mxn];
- 20}A[mxn], *B[mxn];
- 21
- 22inlineboolcmp(data *a, data *b)
- 23 {
- 24 returna->c < b->c;
- 25 }
- 26
- 27 lng G[mxn][mxn];
- 28
- 29inlineboolinsert(data *d)
- 30 {
- 31 for(inti =1; i <= m; ++i)
- 32 if(fabs(d->s[i]) > eps)
- 33 {
- 34 if(fabs(G[i][i]) > eps)
- 35 {
- 36lng k = d->s[i] / G[i][i];
- 37
- 38 for(intj = i; j <= m; ++j)
- 39d->s[j] -= G[i][j] * k;
- 40 }
- 41 else
- 42 {
- 43 for(intj = i; j <= m; ++j)
- 44G[i][j] = d->s[j];
- 45
- 46 return true;
- 47 }
- 48 }
- 49
- 50 return false;
- 51 }
- 52
- 53signed main(void)
- 54 {
- 55scanf("%d%d", &n, &m);
- 56
- 57 for(inti =1; i <= n; ++i)
- 58 for(intj =1; j <= m; ++j)
- 59scanf("%d", &A[i].c), A[i].s[j] = A[i].c;
- 60
- 61 for(inti =1; i <= n; ++i)
- 62scanf("%d", &A[i].c), B[i] = A + i;
- 63
- 64std::sort(B +1, B + n +1, cmp);
- 65
- 66 intcnt =0, ans =0;
- 67
- 68 for(inti =1; i <= n; ++i)
- 69 if (insert(B[i]))
- 70++cnt, ans += B[i]->c;
- 71
- 72printf("%d %d\n", cnt, ans);
- 73}
来源: http://www.bubuko.com/infodetail-1955858.html