QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #32439 | #1461. Greedy Algorithm | cdw# | WA | 289ms | 4204kb | C++20 | 847b | 2022-05-20 09:41:15 | 2022-05-20 09:41:16 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int N = 53, M = 500, K = 50003;
int n, m, a[N][N], f[K], g[K], cnt[1003], ans;
void solve(){
memset(f, 0xC0, sizeof(f));
memset(g, 0xC0, sizeof(g));
f[0] = 0;
for(int i = 0;i < n;++ i){
int tmp = 0, nxt = (i + 1) % n;
memset(cnt, 0, sizeof(cnt));
for(int j = 0;j < m;++ j) ++ cnt[a[nxt][j] - a[i][j] + M];
for(int j = 0;j <= 1000;++ j)
for(int k = 0;k <= 1000 * i;++ k)
g[j + k] = max(g[j + k], f[k] + cnt[j]);
memcpy(f, g, sizeof(f));
}
ans += f[M * n];
}
int main(){
ios::sync_with_stdio(false);
cin >> n >> m;
for(int i = 0;i < n;++ i)
for(int j = 0;j < m;++ j) cin >> a[i][j];
solve();
swap(n, m);
for(int i = 0;i < max(n, m);++ i)
for(int j = i+1;j < max(n, m);++ j)
swap(a[i][j], a[j][i]);
solve();
printf("%d\n", ans);
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 4052kb
input:
2 3 1 2 3 4 5 99
output:
8
result:
ok 1 number(s): "8"
Test #2:
score: 0
Accepted
time: 4ms
memory: 4188kb
input:
3 3 3 2 4 2 2 3 5 4 6
output:
14
result:
ok 1 number(s): "14"
Test #3:
score: 0
Accepted
time: 4ms
memory: 4104kb
input:
5 4 3 6 10 8 0 6 8 8 2 4 5 6 1 5 9 6 3 6 11 12
output:
16
result:
ok 1 number(s): "16"
Test #4:
score: 0
Accepted
time: 0ms
memory: 4056kb
input:
2 5 5 3 6 9 0 4 7 9 4 0
output:
7
result:
ok 1 number(s): "7"
Test #5:
score: 0
Accepted
time: 38ms
memory: 4124kb
input:
2 25 16 78 57 53 34 41 38 99 13 81 57 94 31 83 70 13 54 95 10 4 40 77 7 3 84 99 44 69 4 63 51 8 96 78 75 40 0 71 60 77 64 33 61 49 83 79 68 24 80 89
output:
29
result:
ok 1 number(s): "29"
Test #6:
score: 0
Accepted
time: 146ms
memory: 4128kb
input:
2 50 319 86 426 335 98 216 341 303 475 38 447 159 155 169 471 38 54 78 65 165 214 482 479 243 433 444 232 235 213 314 350 315 144 470 241 174 160 271 497 458 90 45 44 54 195 46 272 308 387 87 378 305 489 14 95 144 460 201 424 418 472 495 60 19 15 483 283 136 392 439 401 26 487 185 377 339 341 281 44...
output:
54
result:
ok 1 number(s): "54"
Test #7:
score: 0
Accepted
time: 1ms
memory: 4116kb
input:
5 3 6 4 10 3 1 1 4 1 7 5 10 7 2 3 9
output:
13
result:
ok 1 number(s): "13"
Test #8:
score: 0
Accepted
time: 39ms
memory: 4156kb
input:
25 3 24 36 59 75 97 18 53 22 62 93 53 64 46 69 18 74 43 30 75 83 24 35 3 36 77 10 68 95 63 76 25 98 63 21 41 85 58 25 45 55 0 35 25 14 74 34 58 3 83 96 12 53 86 52 43 78 13 53 49 40 85 9 47 72 58 4 8 68 25 5 23 32 14 45 20
output:
29
result:
ok 1 number(s): "29"
Test #9:
score: 0
Accepted
time: 146ms
memory: 4076kb
input:
50 3 349 13 253 23 380 4 167 227 371 310 434 383 346 421 289 264 381 438 322 281 186 207 232 301 350 463 126 244 213 137 145 284 21 292 382 441 313 363 146 117 266 397 288 277 199 481 168 454 450 319 282 374 48 352 101 251 439 191 260 108 477 55 266 460 47 441 437 493 55 234 62 220 365 201 15 304 27...
output:
56
result:
ok 1 number(s): "56"
Test #10:
score: 0
Accepted
time: 44ms
memory: 4196kb
input:
17 23 94 58 175 125 214 145 239 172 13 41 226 155 228 81 78 219 51 76 232 177 51 194 223 119 162 109 17 169 67 173 4 201 139 5 127 60 133 27 142 155 143 27 209 67 43 181 157 213 159 139 217 7 37 132 147 128 28 172 57 144 53 97 176 102 39 87 145 88 123 213 199 207 128 134 82 88 8 122 214 68 153 130 9...
output:
58
result:
ok 1 number(s): "58"
Test #11:
score: 0
Accepted
time: 59ms
memory: 4172kb
input:
29 13 266 271 223 265 23 211 237 183 197 243 143 154 12 44 192 164 121 240 240 7 191 55 50 109 17 89 221 96 57 164 252 243 196 220 94 199 196 70 6 199 205 92 236 157 264 60 202 10 2 185 95 258 46 168 96 205 95 37 130 136 255 108 49 146 108 47 77 95 197 55 184 57 209 75 169 185 136 58 11 178 152 104 ...
output:
56
result:
ok 1 number(s): "56"
Test #12:
score: 0
Accepted
time: 286ms
memory: 4076kb
input:
50 50 3 4 4 2 2 5 2 4 3 2 5 1 4 5 5 1 3 0 3 5 4 0 0 0 0 4 3 5 3 4 1 4 2 4 1 0 5 0 2 2 3 0 0 0 2 4 3 2 2 5 1 3 5 4 0 1 0 3 3 5 2 2 5 0 0 0 1 4 1 1 0 3 2 3 5 1 3 1 5 5 0 4 0 1 3 5 4 3 5 5 2 3 5 4 3 2 2 2 0 5 1 5 2 5 5 5 1 4 2 2 1 4 2 2 0 3 5 0 2 0 0 4 4 4 0 2 1 0 4 1 0 0 5 4 1 2 0 1 1 0 1 0 2 3 4 1 4 ...
output:
973
result:
ok 1 number(s): "973"
Test #13:
score: 0
Accepted
time: 284ms
memory: 4076kb
input:
50 50 16 0 30 15 9 24 36 33 6 3 40 7 0 3 30 24 41 31 15 21 40 35 30 22 37 37 22 44 8 29 23 11 45 0 43 1 11 24 35 27 28 7 45 34 37 43 44 49 31 7 1 19 27 26 50 30 44 13 19 41 28 0 22 39 35 49 19 4 2 1 50 22 45 26 13 6 11 33 18 11 4 32 2 16 35 16 6 6 43 31 17 2 43 35 50 16 19 50 21 39 15 20 17 29 8 15 ...
output:
338
result:
ok 1 number(s): "338"
Test #14:
score: 0
Accepted
time: 284ms
memory: 4132kb
input:
50 50 466 446 229 241 470 452 312 103 167 60 40 262 482 318 204 403 287 89 8 92 24 491 153 499 388 96 210 428 128 194 479 141 223 406 338 260 90 459 338 402 134 401 249 43 93 55 263 149 217 432 38 307 488 27 264 286 461 406 376 182 384 205 387 461 270 423 269 156 17 127 191 374 467 305 301 24 465 42...
output:
188
result:
ok 1 number(s): "188"
Test #15:
score: 0
Accepted
time: 158ms
memory: 4204kb
input:
17 50 89 83 53 47 96 61 35 65 33 57 92 87 69 46 41 59 100 72 95 41 50 69 67 40 64 72 55 83 62 72 50 37 72 83 102 62 44 46 64 37 38 60 31 82 71 85 80 43 36 65 84 92 66 80 85 101 74 73 35 79 66 106 102 93 78 74 112 67 104 54 83 58 107 79 72 74 77 57 81 105 97 74 87 95 97 71 57 79 53 77 77 68 33 104 45...
output:
207
result:
ok 1 number(s): "207"
Test #16:
score: 0
Accepted
time: 176ms
memory: 4136kb
input:
50 23 64 104 106 104 139 160 110 120 85 105 49 106 91 123 130 99 92 140 104 83 145 149 116 70 137 133 106 171 111 172 112 110 78 64 161 158 82 85 130 72 154 84 80 122 143 146 122 166 89 192 156 130 161 203 150 90 117 162 150 143 93 159 100 138 137 137 194 207 185 36 76 102 106 142 103 131 115 98 85 ...
output:
197
result:
ok 1 number(s): "197"
Test #17:
score: 0
Accepted
time: 160ms
memory: 4204kb
input:
17 50 37 39 56 74 86 21 48 72 63 35 55 101 46 74 25 25 58 31 51 51 57 59 49 63 63 58 74 89 91 57 66 26 39 88 73 56 52 79 92 20 39 57 63 56 64 76 58 72 42 38 94 50 69 125 109 83 69 110 75 69 74 130 102 100 96 51 87 88 62 64 108 82 111 84 101 70 108 108 120 113 92 97 65 117 130 67 65 130 115 82 60 95 ...
output:
223
result:
ok 1 number(s): "223"
Test #18:
score: 0
Accepted
time: 176ms
memory: 4040kb
input:
50 23 87 91 113 153 145 93 129 107 103 104 76 101 113 94 89 119 92 129 101 133 136 73 73 135 174 137 111 117 178 153 131 127 128 100 125 137 118 113 143 116 153 125 157 160 97 97 117 158 153 135 130 126 123 101 97 98 70 95 107 88 83 113 86 123 95 127 130 67 67 82 126 177 112 142 122 122 100 96 97 69...
output:
1682
result:
ok 1 number(s): "1682"
Test #19:
score: 0
Accepted
time: 167ms
memory: 4068kb
input:
39 37 209 323 275 189 335 309 217 339 315 302 274 280 254 186 404 238 265 216 293 313 304 272 343 241 297 375 361 277 178 281 279 208 201 179 289 286 237 101 215 167 124 277 201 109 181 207 194 118 172 146 61 297 130 159 61 210 264 256 184 273 115 106 252 267 173 70 296 317 115 177 127 181 178 129 2...
output:
1696
result:
ok 1 number(s): "1696"
Test #20:
score: 0
Accepted
time: 285ms
memory: 4132kb
input:
50 50 212 239 347 362 229 188 249 304 150 398 260 271 262 350 194 328 246 273 323 242 276 307 308 295 252 280 300 216 263 232 199 258 350 324 186 374 268 242 273 235 307 273 355 305 268 266 258 297 328 179 110 201 234 163 124 135 134 277 182 289 87 175 173 199 253 240 114 242 198 178 213 291 239 302...
output:
255
result:
ok 1 number(s): "255"
Test #21:
score: 0
Accepted
time: 288ms
memory: 4060kb
input:
50 50 211 203 376 250 270 321 309 212 152 350 186 256 309 142 142 196 364 246 349 269 287 237 363 176 359 230 395 324 297 227 256 252 347 183 292 215 232 367 281 299 210 275 211 287 281 407 284 340 265 232 114 199 225 166 178 193 254 89 49 224 126 219 134 66 80 158 184 203 178 56 161 108 240 184 262...
output:
309
result:
ok 1 number(s): "309"
Test #22:
score: 0
Accepted
time: 288ms
memory: 4136kb
input:
50 50 150 236 302 172 270 100 178 339 267 259 172 261 281 188 204 172 250 198 179 316 311 319 210 207 257 204 167 265 190 184 224 279 228 334 278 289 285 301 171 313 299 371 263 335 197 309 166 363 219 324 224 346 322 289 286 164 216 257 263 251 152 387 391 254 185 222 304 214 296 219 199 249 226 33...
output:
825
result:
ok 1 number(s): "825"
Test #23:
score: 0
Accepted
time: 289ms
memory: 4204kb
input:
50 50 275 213 228 224 320 186 293 266 232 221 333 195 218 157 185 137 197 277 318 274 267 272 188 287 222 234 152 154 184 107 197 208 236 63 93 93 243 102 104 123 227 225 220 208 248 164 253 319 291 261 189 200 215 287 307 173 201 258 194 236 188 103 205 153 165 51 279 264 238 141 254 293 175 300 23...
output:
1397
result:
ok 1 number(s): "1397"
Test #24:
score: 0
Accepted
time: 281ms
memory: 4132kb
input:
50 50 328 279 231 318 225 200 235 253 272 153 238 157 194 166 183 229 239 227 135 157 222 284 271 259 217 232 261 234 182 307 277 331 319 340 271 276 280 160 192 114 197 126 123 299 227 215 163 337 264 263 288 239 199 261 185 160 195 213 266 147 133 206 130 126 143 189 199 187 108 117 182 244 231 21...
output:
2628
result:
ok 1 number(s): "2628"
Test #25:
score: 0
Accepted
time: 285ms
memory: 4064kb
input:
50 50 187 120 217 174 200 253 261 179 123 292 203 266 226 170 129 131 116 249 152 187 252 139 128 103 232 263 213 161 236 132 201 234 120 216 214 161 177 141 182 220 109 67 170 162 211 104 247 209 168 177 248 181 306 235 261 314 322 276 184 266 195 327 287 204 190 215 177 310 217 252 313 200 189 164...
output:
3727
result:
ok 1 number(s): "3727"
Test #26:
score: 0
Accepted
time: 281ms
memory: 4088kb
input:
50 50 208 181 182 174 248 166 166 256 284 197 230 284 218 286 262 262 171 214 232 270 273 267 238 182 193 230 174 251 199 202 162 220 232 168 234 171 172 265 221 172 177 219 154 237 292 297 293 214 175 189 129 102 103 95 169 87 87 177 205 118 151 205 139 207 183 183 92 135 153 191 194 188 159 103 11...
output:
4984
result:
ok 1 number(s): "4984"
Test #27:
score: 0
Accepted
time: 289ms
memory: 4152kb
input:
50 50 177 148 247 214 186 275 249 231 243 139 277 140 237 268 170 240 159 230 190 194 140 181 270 266 248 257 220 242 257 238 166 253 186 162 268 232 227 209 225 163 270 254 255 226 212 139 288 177 169 226 238 209 308 275 247 336 310 292 304 200 338 201 298 329 231 301 220 291 251 255 201 242 331 32...
output:
5000
result:
ok 1 number(s): "5000"
Test #28:
score: 0
Accepted
time: 288ms
memory: 4040kb
input:
50 50 137 226 210 131 238 259 302 180 221 277 292 118 160 259 335 232 348 289 178 139 268 212 213 191 210 246 193 244 300 161 211 121 119 213 201 321 267 237 322 139 236 169 193 243 326 115 278 264 213 169 93 134 126 99 215 105 115 9 159 105 152 126 88 157 229 150 273 163 242 13 122 122 173 241 114 ...
output:
261
result:
ok 1 number(s): "261"
Test #29:
score: 0
Accepted
time: 288ms
memory: 4000kb
input:
50 50 329 247 255 279 138 273 269 189 352 286 330 299 281 241 169 277 338 317 198 325 236 239 298 278 352 318 358 154 261 250 344 275 348 254 205 260 247 341 288 254 308 217 274 339 302 254 287 233 316 258 264 322 119 320 189 331 255 251 408 276 246 165 295 225 148 272 316 245 292 248 348 295 307 29...
output:
315
result:
ok 1 number(s): "315"
Test #30:
score: 0
Accepted
time: 284ms
memory: 4064kb
input:
50 50 359 347 387 426 248 241 275 279 175 309 349 362 321 194 328 341 366 179 276 293 298 249 226 306 333 275 318 202 309 314 370 201 303 311 339 287 357 255 353 332 199 300 280 320 342 341 327 321 305 309 254 230 281 347 155 89 195 199 70 229 269 282 328 148 248 136 181 148 252 134 201 138 286 259 ...
output:
841
result:
ok 1 number(s): "841"
Test #31:
score: 0
Accepted
time: 285ms
memory: 4112kb
input:
50 50 196 92 121 157 161 123 108 145 78 209 96 130 182 187 240 166 67 156 52 276 193 197 287 188 190 190 207 106 243 102 213 148 275 151 152 110 237 66 115 175 109 175 183 138 171 139 115 141 196 153 171 167 147 306 209 146 260 140 174 230 282 148 272 251 332 302 234 190 216 307 327 214 261 274 301 ...
output:
1402
result:
ok 1 number(s): "1402"
Test #32:
score: 0
Accepted
time: 285ms
memory: 4112kb
input:
50 50 224 283 196 271 245 277 155 115 137 136 138 163 240 118 123 263 304 263 79 158 205 235 218 133 98 168 137 123 170 170 192 282 302 176 295 277 307 305 252 229 133 207 101 194 324 246 283 256 116 252 281 329 294 230 344 303 254 214 235 236 252 284 361 217 206 362 361 328 178 257 274 290 380 334 ...
output:
2627
result:
ok 1 number(s): "2627"
Test #33:
score: 0
Accepted
time: 289ms
memory: 4116kb
input:
50 50 121 113 122 115 168 106 38 136 113 61 143 124 35 183 82 179 107 122 183 80 63 178 159 74 80 32 79 31 62 104 170 115 39 91 137 104 95 178 119 150 117 150 134 138 135 186 187 176 60 168 181 173 182 175 228 166 98 196 173 121 203 184 95 243 142 239 167 182 243 140 123 238 219 134 140 92 139 91 12...
output:
4916
result:
ok 1 number(s): "4916"
Test #34:
score: 0
Accepted
time: 288ms
memory: 4164kb
input:
50 50 330 447 318 359 400 460 299 458 312 345 325 351 398 444 343 367 405 380 421 429 379 371 419 311 457 353 302 397 429 426 358 297 368 389 321 414 405 369 329 344 322 382 341 416 325 310 310 462 361 309 297 414 285 326 367 427 266 425 279 312 292 318 365 411 310 334 372 347 388 396 346 338 386 27...
output:
4996
result:
ok 1 number(s): "4996"
Test #35:
score: -100
Wrong Answer
time: 266ms
memory: 4068kb
input:
48 48 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 500 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...
output:
1752
result:
wrong answer 1st numbers differ - expected: '2280', found: '1752'