link

期末考试

发现答案只和maxbi\max b_i有关,于是从大到小枚举maxbi\max b_i,动态维护一下各个部分的信息即可,具体细节很简单,就不赘述了

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <climits>
#include <queue>
#include <set>
#include <cmath>
#include <map>
#include <bitset>
#include <fstream>
#include <tr1/unordered_map>
#include <assert.h>

#define x first
#define y second
#define y0 Y0
#define y1 Y1
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
return sum * fl;
}

inline void proc_status ()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int MAXN = 1e5;

int N, M, a, b, c;
int T[MAXN + 5], B[MAXN + 5];
LL sum1, sum2;

namespace S1
{
int bkt[MAXN + 5];

int up_delta, down_delta;
LL up, down;

inline void update (int x)
{
up_delta += bkt[x];
up += up_delta;
down_delta -= bkt[x];
down -= down_delta;

if (a >= b) sum1 = up * b;
else sum1 = min (up, down) * a + max (0ll, up - down) * b;
}

inline void init ()
{
for (int i = 1; i <= M; ++i) down += MAXN - B[i], ++bkt[B[i]];
down_delta = M;
}
}

namespace S2
{
int bkt[MAXN + 5], delta;

inline void update (int x)
{
delta -= bkt[x];
sum2 -= delta;
}

inline void init ()
{
delta = N;
for (int i = 1; i <= N; ++i) sum2 += MAXN - T[i], ++bkt[T[i]];
}
}

inline void Solve ()
{
LL ans = LLONG_MAX;
S1 :: init(), S2 :: init ();

for (int i = MAXN; i >= 0; --i)
{
Chkmin (ans, sum1 + sum2 * c);
S1 :: update (i);
S2 :: update (i);
}

cout << ans << endl;
}

inline void Input ()
{
a = read<int>(), b = read<int>(), c = read<int>();
N = read<int>(), M = read<int>();
for (int i = 1; i <= N; ++i) T[i] = read<int>();
for (int i = 1; i <= M; ++i) B[i] = read<int>();
}

int main ()
{

#ifdef hk_cnyali
freopen("A.in", "r", stdin);
freopen("A.out", "w", stdout);
#endif

Input ();
Solve ();

return 0;
}

相逢是问候

扩展欧拉定理:


因为递归层数只有O(logp)O(\log p), 预处理出pp经过多少次变成11,设为limlim

考虑用线段树维护,和区间开根类似,对每个点记录总共被修改了多少次(设为cntcnt)。修改的时候如果区间cntcnt的最小值比limlim大,那么这个区间就不用管了,否则递归到每个叶子上暴力修改

但直接做是O(nlog3n)O(n\log^3 n)的,因为快速幂有个log\log。注意到这里只要求cc的若干次方,考虑预处理10410^4内的答案和104×i10^4 \times i的答案,这样就可以O(1)O(1)快速幂了

还有一个地方需要注意,因为扩展欧拉定理中的指数是不能取模的,并且我们需要判断指数是否φ(p)\ge \varphi(p)。我的做法是预处理一个数组存cc0600 \sim 60次方的结果(因为小于φ(p)\varphi(p)的指数不可能超过6060),若大于10810^8则为1-1。当上一步递归的结果60\le 60时就用这个值来判断即可

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <climits>
#include <queue>
#include <set>
#include <cmath>
#include <map>
#include <bitset>
#include <fstream>
#include <tr1/unordered_map>
#include <assert.h>

#define x first
#define y second
#define y0 Y0
#define y1 Y1
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
return sum * fl;
}

inline void proc_status ()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int MAXN = 5e4;
const int MAX_LOG = 60;

int N, M, MOD, C, A[MAXN + 5];
int phi[MAX_LOG + 5], LOG;

namespace MATH
{
inline int Pow (int a, int b, int mod)
{
int ans = 1;
for (int i = b; i; i >>= 1, a = (LL) a * a % mod) if (i & 1) ans = (LL) ans * a % mod;
return ans;
}

namespace POW
{
const int B = 1e4;

int pw[2][B + 5][MAX_LOG + 1];

inline void init ()
{
for (int i = 0; i <= B; ++i)
for (int j = 0; j <= LOG; ++j)
pw[0][i][j] = Pow (C, i, phi[j]);
for (int i = 0; i <= B; ++i)
for (int j = 0; j <= LOG; ++j)
pw[1][i][j] = Pow (Pow (C, B, phi[j]), i, phi[j]);
}

inline int get_pow (int x, int k) { return (LL) pw[1][x / B][k] * pw[0][x % B][k] % phi[k]; }
}

using POW :: get_pow;

int pw[MAXN + 5];

inline int get_phi (int n)
{
int ans = n;
for (int i = 2; i * i <= n; ++i) if (!(n % i))
{
ans = (LL) ans * (i - 1) / i;
while (!(n % i)) n /= i;
}
if (n != 1) ans = (LL) ans * (n - 1) / n;
return ans;
}

inline int calc (int x, int times)
{
int exp = x;
for (int i = times - 1; i >= 0; --i)
{
if (exp == -1 || exp >= phi[i + 1])
{
x = get_pow (x % phi[i + 1] + phi[i + 1], i);
exp = -1;
}
else
{
x = get_pow (x, i);
if (exp <= MAX_LOG) exp = pw[exp];
else exp = -1;
}
}
return x;
}

inline void init ()
{
for (phi[0] = MOD, LOG = 1; phi[LOG - 1] != 1; ++LOG) phi[LOG] = get_phi (phi[LOG - 1]);
phi[LOG] = get_phi (phi[LOG - 1]);

pw[0] = 1;
for (int i = 1; i <= MAX_LOG; ++i)
{
LL res = (LL) pw[i - 1] * C;
if (0 <= res && res <= 1e8) pw[i] = res;
else pw[i] = -1;
}

POW :: init ();
}
}

using namespace MATH;

namespace SEG
{
#define mid ((l + r) >> 1)
#define ls o << 1
#define rs o << 1 | 1
#define lson ls, l, mid
#define rson rs, mid + 1, r

const int MAXN = :: MAXN * 4;

struct info
{
int sum, cnt;
} node[MAXN + 5];

inline void push_up (int o)
{
node[o].sum = (node[ls].sum + node[rs].sum) % MOD;
node[o].cnt = min (node[ls].cnt, node[rs].cnt);
}

inline void build (int o, int l, int r)
{
if (l == r) return void (node[o].sum = A[l]);
build (lson), build (rson);
push_up (o);
}

inline int query (int o, int l, int r, int x, int y)
{
if (x <= l && r <= y) return node[o].sum;
if (x > mid) return query (rson, x, y);
if (y <= mid) return query (lson, x, y);
return (query (lson, x, y) + query (rson, x, y)) % MOD;
}

inline void update (int o, int l, int r, int x, int y)
{
if (node[o].cnt >= LOG) return ;
if (l == r)
{
++node[o].cnt;
node[o].sum = calc (A[l], node[o].cnt);
return ;
}
if (x <= mid) update (lson, x, y);
if (y > mid) update (rson, x, y);
push_up (o);
}
#undef mid
}

inline void Solve ()
{
MATH :: init ();
SEG :: build (1, 1, N);

while (M--)
{
int op = read<int>(), l = read<int>(), r = read<int>();
if (op == 0) SEG :: update (1, 1, N, l, r);
else printf("%d\n", SEG :: query (1, 1, N, l, r));
}
}

inline void Input ()
{
N = read<int>(), M = read<int>(), MOD = read<int>(), C = read<int>();
for (int i = 1; i <= N; ++i) A[i] = read<int>();
}

int main ()
{

#ifdef hk_cnyali
freopen("A.in", "r", stdin);
freopen("A.out", "w", stdout);
#endif

Input ();
Solve ();

return 0;
}

组合数问题

注意到题意就是从n×kn \times k个物品中选出 kkrr 个物品的方案数

直接DP设f(i,j)f(i, j)表示到第ii个物品,选出模kkjj个物品的方案数,矩阵快速幂优化即可

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <climits>
#include <queue>
#include <set>
#include <cmath>
#include <map>
#include <bitset>
#include <fstream>
#include <tr1/unordered_map>
#include <assert.h>

#define x first
#define y second
#define y0 Y0
#define y1 Y1
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
return sum * fl;
}

inline void proc_status ()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int MAXN = 50;

int N, MOD, K, R;

inline void ADD (int &a, int b) { if ((a += b) >= MOD) a -= MOD; }

struct matrix
{
int A[MAXN + 5][MAXN + 5];

inline matrix () { memset (A, 0, sizeof A); }

inline int* operator [] (const int &x) { return A[x]; }

inline matrix operator * (const matrix &rhs) const
{
matrix now;
for (int i = 0; i < K; ++i)
for (int k = 0; k < K; ++k) if (A[i][k])
for (int j = 0; j < K; ++j)
ADD (now.A[i][j], (LL) A[i][k] * rhs.A[k][j] % MOD);
return now;
}

};

inline void Solve ()
{
matrix ans;
ans[0][0] = 1;

matrix trans;
for (int i = 0; i < K; ++i) ++trans[i][i], ++trans[(i - 1 + K) % K][i];

for (LL i = (LL) N * K; i; i >>= 1, trans = trans * trans) if (i & 1) ans = ans * trans;

cout << ans[0][R] << endl;
}

inline void Input ()
{
N = read<int>(), MOD = read<int>(), K = read<int>(), R = read<int>();
}

int main ()
{

#ifdef hk_cnyali
freopen("A.in", "r", stdin);
freopen("A.out", "w", stdout);
#endif

Input ();
Solve ();

return 0;
}

摧毁“树状图”

好恶心的分类讨论

f[x][0/1][0/1][0/1/2]f[x][0/1][0/1][0/1/2]表示xx子树中,xx是否删,xx是否还有一条可以接着往上连的边(即xx在选路径方案中度数的奇偶性),已经选了0/1/20/1/2条边时,最多的联通块数目

实际上只有66个状态是有用的,手动分类讨论一下转移即可

在转移时还需要记录两个量: sonson表示已经考虑完了几棵子树, resres表示在删xx的条件下,当前子树中只有1条路径的最多联通块数目

具体转移见代码

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <climits>
#include <queue>
#include <set>
#include <cmath>
#include <map>
#include <bitset>
#include <fstream>
#include <tr1/unordered_map>
#include <assert.h>

#define x first
#define y second
#define y0 Y0
#define y1 Y1
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
return sum * fl;
}

inline void proc_status ()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

template <typename T, typename A, typename ...B> inline void Chkmax (T &val, A x, B ...y) { Chkmax (val, x); Chkmax (val, y...); }

const int MAXN = 1e5;

int N, X;
int e, Begin[MAXN + 5], To[MAXN * 2 + 5], Next[MAXN * 2 + 5];
int F[MAXN + 5][2][2][3];

inline void add_edge (int x, int y) { To[++e] = y; Next[e] = Begin[x]; Begin[x] = e; }

inline void dfs (int x, int fa)
{
for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) for (int k = 0; k < 3; ++k) F[x][i][j][k] = 0;

int son = 0, res = 0;

for (int t = Begin[x]; t; t = Next[t])
{
int y = To[t];
if (y == fa) continue;
dfs (y, x);

static int h[2][2][3];
auto f = F[x], g = F[y];
int now = max (g[0][0][1], max (g[1][0][1], g[1][1][1]));

for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) for (int k = 0; k < 3; ++k) h[i][j][k] = 0;

Chkmax (h[0][0][1], g[0][0][1], g[1][0][1] + 1, g[1][1][1] + 1);
Chkmax (h[0][0][2], g[0][0][2], g[1][0][2] + 1, g[1][1][2] + 1, f[0][0][1] + h[0][0][1] - 1);
Chkmax (h[1][0][1], f[1][1][1] + g[1][1][1]);
Chkmax (h[1][0][2], f[1][0][1] + max (g[0][0][1], g[1][0][1]), f[1][1][2] + g[1][1][1], f[1][1][1] + g[1][1][2]);
Chkmax (h[1][1][1], g[1][1][1] + son);
Chkmax (h[1][1][2], g[1][1][2] + son, f[1][1][1] + now, max (res, f[1][0][1]) + g[1][1][1]);

res = max (res + 1, son + now);
++son;

for (int i = 0; i < 2; ++i) for (int j = 0; j < 2; ++j) for (int k = 0; k < 3; ++k)
F[x][i][j][k] = max (F[x][i][j][k] + i, h[i][j][k]);
}


Chkmax (F[x][1][1][1], son);
}

inline void Solve ()
{
dfs (1, 0);

int ans = 0;
Chkmax (ans, F[1][0][0][2], F[1][1][0][2], F[1][1][1][2]);

printf("%d\n", ans);
}

inline void Input ()
{
N = read<int>(); for (int i = 1; i <= 2 * X; ++i) read<int>();

for (int i = 1; i < N; ++i)
{
int x = read<int>(), y = read<int>();
add_edge (x, y);
add_edge (y, x);
}
}

inline void Init ()
{
e = 0;
for (int i = 1; i <= N; ++i) Begin[i] = 0;
}

int main ()
{

#ifdef hk_cnyali
freopen("A.in", "r", stdin);
freopen("A.out", "w", stdout);
#endif

int Te = read<int>(); X = read<int>();

while (Te--)
{
Input ();
Solve ();
Init ();
}

return 0;
}

分手是祝愿

solution

寿司餐厅

最大权闭合子图模板题

注意到题意即为: 要选择di,jd_{i, j},就必须先选di+1,jd_{i + 1, j}di,j1d_{i, j - 1}di,id_{i, i}还要多付出aia_i的代价

此外,对每种类型xx的寿司额外建一个点,权值为x2x^2。若选了di,id_{i, i},就必须选类型aia_i

Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
#include <iostream>
#include <ctime>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <climits>
#include <queue>
#include <set>
#include <cmath>
#include <map>
#include <bitset>
#include <fstream>
#include <tr1/unordered_map>
#include <assert.h>

#define x first
#define y second
#define y0 Y0
#define y1 Y1
#define mp make_pair
#define pb push_back
#define DEBUG(x) cout << #x << " = " << x << endl;

using namespace std;

typedef long long LL;
typedef pair <int, int> pii;

template <typename T> inline int Chkmax (T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline int Chkmin (T &a, T b) { return a > b ? a = b, 1 : 0; }
template <typename T> inline T read ()
{
T sum = 0, fl = 1; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') fl = -1;
for (; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
return sum * fl;
}

inline void proc_status ()
{
ifstream t ("/proc/self/status");
cerr << string (istreambuf_iterator <char> (t), istreambuf_iterator <char> ()) << endl;
}

const int MAXN = 100;
const int MAXM = 1000;

int N, M, Ty;
int A[MAXN + 5], D[MAXN + 5][MAXN + 5];

namespace FLOW
{
const int MAXN = :: MAXN * :: MAXN + :: MAXM;
const int MAXM = 2e6;

int e, Begin[MAXN + 5], To[MAXM + 5], Next[MAXM + 5], W[MAXM + 5];
int Cur[MAXN + 5];
int S = 0, T = MAXN + 1;

inline void add_edge (int x, int y, int z) { To[++e] = y; Next[e] = Begin[x]; Begin[x] = e; W[e] = z; }

inline void add (int x, int y, int z) { add_edge (x, y, z), add_edge (y, x, 0); }

int dis[MAXN + 5];

inline int bfs ()
{
for (int i = S; i <= T; ++i) dis[i] = -1;
dis[S] = 0;

static queue <int> Q; Q.push (S);

while (!Q.empty())
{
int x = Q.front(); Q.pop();
for (int i = Begin[x]; i; i = Next[i])
{
int y = To[i];
if (dis[y] == -1 && W[i] > 0)
{
dis[y] = dis[x] + 1;
Q.push (y);
}
}
}

return dis[T] != -1;
}

inline int dfs (int x, int k)
{
if (x == T || !k) return k;

int sum = 0;
for (int &i = Cur[x]; i; i = Next[i])
{
int y = To[i], tmp;
if (dis[y] == dis[x] + 1 && W[i] > 0 && (tmp = dfs (y, min (k, W[i]))))
{
W[i] -= tmp, W[i ^ 1] += tmp;
k -= tmp, sum += tmp;
if (!k) return sum;
}
}
return sum;
}

inline LL work ()
{
LL ans = 0;
while (bfs ())
{
for (int i = S; i <= T; ++i) Cur[i] = Begin[i];
ans += dfs (S, INT_MAX);
}
return ans;
}

inline void init ()
{
e = 1;
memset (Begin, 0, sizeof Begin);
}
}

using FLOW :: S;
using FLOW :: T;

inline void Solve ()
{
FLOW :: init ();

LL ans = 0;

if (Ty) for (int i = 1; i <= M; ++i) FLOW :: add (i, T, i * i);

static int Id[MAXN + 5][MAXN + 5];
int id_cnt = M;

for (int i = 1; i <= N; ++i)
for (int j = i; j <= N; ++j)
Id[i][j] = ++id_cnt;

for (int len = 1; len <= N; ++len)
{
for (int i = 1; i + len - 1 <= N; ++i)
{
int j = i + len - 1;
if (len == 1)
{
if (D[i][i] - A[i] >= 0) FLOW :: add (S, Id[i][i], D[i][i] - A[i]), ans += D[i][i] - A[i];
else FLOW :: add (Id[i][i], T, A[i] - D[i][i]);

if (Ty) FLOW :: add (Id[i][i], A[i], INT_MAX);
}
else
{
if (D[i][j] >= 0) FLOW :: add (S, Id[i][j], D[i][j]), ans += D[i][j];
else FLOW :: add (Id[i][j], T, -D[i][j]);

FLOW :: add (Id[i][j], Id[i + 1][j], INT_MAX);
FLOW :: add (Id[i][j], Id[i][j - 1], INT_MAX);
}
}
}

ans -= FLOW :: work ();
cout << ans << endl;
}

inline void Input ()
{
N = read<int>(), Ty = read<int>();
for (int i = 1; i <= N; ++i) Chkmax (M, A[i] = read<int>());
for (int i = 1; i <= N; ++i)
for (int j = i; j <= N; ++j)
D[i][j] = read<int>();
}

int main ()
{

#ifdef hk_cnyali
freopen("A.in", "r", stdin);
freopen("A.out", "w", stdout);
#endif

Input ();
Solve ();

return 0;
}