QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#139036#3005. Monotonykaruna#AC ✓1218ms159292kbC++171.4kb2023-08-12 16:46:532023-08-12 16:46:56

Judging History

你现在查看的是最新测评结果

  • [2023-08-12 16:46:56]
  • 评测
  • 测评结果：AC
  • 用时：1218ms
  • 内存：159292kb
查看
  • [2023-08-12 16:46:53]
  • 提交

answer

#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 20;

int n, m, a[MAXN][MAXN], diff[MAXN][MAXN];

ll dp[MAXN][1 << MAXN];
int main() {
	cin.tie(0); ios_base::sync_with_stdio(0);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> a[i][j];
		}
	}
	for (int i1 = 0; i1 < n; i1++) {
		for (int i2 = 0; i2 < n; i2++) {
			for (int j = 0; j < m; j++)
				diff[i1][i2] ^= (a[i1][j] < a[i2][j]) << j;
		}
	}
	ll ans = 0;
	for (int j = 1; j < (1 << m); j++) {
		int msk = 0;
		for (int i = 0; i < n; i++) {
			bool inc = true;
			bool dec = true;
			int x = -1;
			for (int p = 0; p < m; p++) if (j >> p & 1) {
				if (x != -1) {
					if (x > a[i][p]) inc = false;
					if (x < a[i][p]) dec = false;
				}
				x = a[i][p];
			}
			if (inc || dec) msk ^= (1 << i);
		}
		for (int i2 = 0; i2 < n; i2++) if (msk >> i2 & 1) {
			for (int i1 = 0; i1 < i2; i1++) if (msk >> i1 & 1) {
				dp[i2][diff[i1][i2] & j] += dp[i1][diff[i1][i2] & j] + 1;
			}
		}
		ans += __builtin_popcount(msk);
		for (int i2 = 0; i2 < n; i2++) if (msk >> i2 & 1) {
			for (int i1 = 0; i1 < i2; i1++) if (msk >> i1 & 1) {
				ans += dp[i2][diff[i1][i2] & j];
				dp[i2][diff[i1][i2] & j] = 0;
			}
		}
	}
	cout << ans;
}
源文件, 语言: C++17

詳細信息

Test #1:

score: 100
Accepted
time: 94ms
memory: 5228kb

input:

13 17
155 221 29 114 165 175 120 107 27 134 125 116 11 56 100 20 15
88 128 38 111 198 212 173 136 44 164 64 150 83 19 93 197 194
219 25 16 50 2 55 151 34 163 76 217 209 141 174 80 144 159
60 156 54 149 97 28 102 145 26 35 188 160 65 152 135 6 21
8 62 195 70 127 30 171 205 147 177 210 117 10 103 161 ...

output:

40490

result:

ok answer is '40490'

Test #2:

score: 0
Accepted
time: 7ms
memory: 4004kb

input:

17 13
41 205 162 42 35 147 143 185 89 176 4 103 181
85 115 59 2 182 190 20 142 97 172 31 211 101
154 62 119 82 16 117 1 157 72 3 149 216 21
188 49 202 77 161 160 169 46 79 133 50 113 91
30 71 156 193 92 29 54 187 111 199 80 22 17
209 122 138 127 135 81 53 86 158 145 109 56 6
150 40 15 212 10 186 32 ...

output:

35799

result:

ok answer is '35799'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3416kb

input:

1 1
1

output:

1

result:

ok answer is '1'

Test #4:

score: 0
Accepted
time: 1ms
memory: 3408kb

input:

1 2
1 2

output:

3

result:

ok answer is '3'

Test #5:

score: 0
Accepted
time: 1ms
memory: 3400kb

input:

1 2
2 1

output:

3

result:

ok answer is '3'

Test #6:

score: 0
Accepted
time: 61ms
memory: 3480kb

input:

1 20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

output:

1048575

result:

ok answer is '1048575'

Test #7:

score: 0
Accepted
time: 1ms
memory: 3468kb

input:

2 1
1
2

output:

3

result:

ok answer is '3'

Test #8:

score: 0
Accepted
time: 1ms
memory: 3608kb

input:

2 1
2
1

output:

3

result:

ok answer is '3'

Test #9:

score: 0
Accepted
time: 1ms
memory: 3588kb

input:

2 2
1 2
3 4

output:

9

result:

ok answer is '9'

Test #10:

score: 0
Accepted
time: 1ms
memory: 3568kb

input:

2 2
1 3
4 2

output:

9

result:

ok answer is '9'

Test #11:

score: 0
Accepted
time: 1ms
memory: 3468kb

input:

2 2
2 1
4 3

output:

9

result:

ok answer is '9'

Test #12:

score: 0
Accepted
time: 1ms
memory: 3472kb

input:

2 2
3 2
4 1

output:

9

result:

ok answer is '9'

Test #13:

score: 0
Accepted
time: 1ms
memory: 3416kb

input:

2 2
4 3
2 1

output:

9

result:

ok answer is '9'

Test #14:

score: 0
Accepted
time: 1ms
memory: 3500kb

input:

4 4
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16

output:

225

result:

ok answer is '225'

Test #15:

score: 0
Accepted
time: 1ms
memory: 3392kb

input:

4 4
1 2 3 4
8 7 6 5
9 10 11 12
16 15 14 13

output:

225

result:

ok answer is '225'

Test #16:

score: 0
Accepted
time: 1ms
memory: 3548kb

input:

4 4
4 5 1 3
11 6 13 10
16 2 9 8
14 15 12 7

output:

110

result:

ok answer is '110'

Test #17:

score: 0
Accepted
time: 1ms
memory: 3660kb

input:

20 1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

output:

1048575

result:

ok answer is '1048575'

Test #18:

score: 0
Accepted
time: 228ms
memory: 44392kb

input:

20 19
180 179 178 177 176 175 174 173 172 190 189 188 187 186 185 184 183 182 181
161 160 159 158 157 156 155 154 153 171 170 169 168 167 166 165 164 163 162
142 141 140 139 138 137 136 135 134 152 151 150 149 148 147 146 145 144 143
123 122 121 120 119 118 117 116 115 133 132 131 130 129 128 127 12...

output:

3485104

result:

ok answer is '3485104'

Test #19:

score: 0
Accepted
time: 213ms
memory: 81256kb

input:

20 19
9 8 7 6 5 4 3 2 1 19 18 17 16 15 14 13 12 11 10
28 27 26 25 24 23 22 21 20 38 37 36 35 34 33 32 31 30 29
47 46 45 44 43 42 41 40 39 57 56 55 54 53 52 51 50 49 48
66 65 64 63 62 61 60 59 58 76 75 74 73 72 71 70 69 68 67
85 84 83 82 81 80 79 78 77 95 94 93 92 91 90 89 88 87 86
104 103 102 101 10...

output:

1702885800

result:

ok answer is '1702885800'

Test #20:

score: 0
Accepted
time: 490ms
memory: 44464kb

input:

20 19
172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190
153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171
134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152
115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 13...

output:

1125119902

result:

ok answer is '1125119902'

Test #21:

score: 0
Accepted
time: 1070ms
memory: 159292kb

input:

20 20
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
10...

output:

1099509530625

result:

ok answer is '1099509530625'

Test #22:

score: 0
Accepted
time: 1218ms
memory: 8180kb

input:

20 20
56 358 43 382 339 146 206 335 390 285 57 35 252 147 378 106 352 395 129 214
308 166 167 359 207 244 77 181 148 158 227 34 200 125 342 93 122 95 377 228
79 26 268 253 192 84 70 301 384 231 171 198 126 137 237 185 310 242 246 153
115 168 203 346 96 399 306 32 215 138 176 360 303 101 275 332 177 ...

output:

153561

result:

ok answer is '153561'
English 繁體中文 简体中文

伺服器時間: 2025-02-01 17:51:59 | 開源專案