QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#812099 | #3283. Parallel Lines | rlc202204 | AC ✓ | 65ms | 4504kb | C++14 | 1.7kb | 2024-12-13 11:31:10 | 2024-12-13 11:31:17 |
Judging History
answer
#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20;
const int MS = (1 << 16) + 5;
const int inf = ~0x3f3f3f3f;
int n;
struct Pnt {
int x, y;
Pnt (int _x = 0, int _y = 0) :
x(_x), y(_y) {}
} p[N];
Pnt operator-(Pnt u, Pnt v) {
return Pnt(u.x - v.x, u.y - v.y);
}
int operator*(Pnt u, Pnt v) {
return u.x * v.y - u.y * v.x;
}
Pnt all[N][N];
bool pal[N][N][N][N] = {{{{false}}}};
int g[MS] = {0};//g[S] ?? S ?????
int cnt[MS] = {0};
int f[MS] = {0};//?????
void cmx(int &x, int y) {
x = max(x, y);
}
void calc(int a, int b) {
memset(f, ~0x3f, sizeof f);
f[0] = 0;
for (int S = 0; S < (1 << n); S++) {
if (f[S] == inf)
continue;
cmx(g[S], f[S]);
for (int i = 1; i <= n; i++)
if (!(S >> (i - 1) & 1))
for (int j = 1; j <= n; j++)
if (i != j && !(S >> (j - 1) & 1) && pal[a][b][i][j])
cmx(f[S | (1 << (i - 1)) | (1 << (j - 1))], f[S] + cnt[S]);
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++)
cin >> p[i].x >> p[i].y;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
all[i][j] = p[i] - p[j];
for (int a = 1; a <= n; a++)
for (int b = 1; b <= n; b++)
for (int c = 1; c <= n; c++)
for (int d = 1; d <= n; d++)
if (all[a][b] * all[c][d] == 0)
pal[a][b][c][d] = true;
for (int S = 0; S < (1 << n); S++)
cnt[S] = __builtin_popcount(S) / 2;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i != j)
calc(i, j);
memset(f, ~0x3f, sizeof f);
f[0] = 0;
for (int S = 0; S < (1 << n); S++) {
for (int T = S; T != 0; T = ((T - 1) & S))
cmx(f[S], f[S - T] + g[T]);
}
cout << f[(1 << n) - 1] << endl;
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3876kb
input:
6 0 0 0 5 3 -2 3 5 5 0 5 7
output:
3
result:
ok single line: '3'
Test #2:
score: 0
Accepted
time: 61ms
memory: 4336kb
input:
16 512 -867 198 -615 134 -269 587 691 -303 -57 708 937 411 354 -724 108 628 897 553 657 356 -536 671 906 342 285 658 -794 -754 93 675 910
output:
9
result:
ok single line: '9'
Test #3:
score: 0
Accepted
time: 62ms
memory: 4260kb
input:
16 955 -856 815 -179 988 -823 -209 39 934 -533 -686 -437 -850 -213 372 -612 867 -600 -990 960 372 -522 -768 -970 -205 43 -990 987 -850 -301 815 -269
output:
9
result:
ok single line: '9'
Test #4:
score: 0
Accepted
time: 58ms
memory: 4248kb
input:
16 726 502 905 -385 484 371 889 324 182 -312 200 -120 808 502 457 18 304 -184 317 -184 -565 345 565 371 116 -120 821 -469 -580 330 877 312
output:
9
result:
ok single line: '9'
Test #5:
score: 0
Accepted
time: 61ms
memory: 4504kb
input:
16 -67 -723 254 963 213 -578 -412 -335 -212 -235 191 -589 -981 219 -202 210 242 -720 -989 215 -168 3 -206 -16 -137 -758 201 804 -324 149 -302 856
output:
15
result:
ok single line: '15'
Test #6:
score: 0
Accepted
time: 63ms
memory: 4384kb
input:
16 162 571 -699 -559 645 507 -976 633 519 320 -822 710 70 525 317 -829 694 -832 408 -782 -867 -643 784 -787 356 -808 569 470 221 -877 529 449
output:
21
result:
ok single line: '21'
Test #7:
score: 0
Accepted
time: 65ms
memory: 4420kb
input:
16 -805 -254 -989 521 -232 -357 -517 -40 483 916 681 659 916 706 -879 543 -200 -350 203 -270 -792 -95 -12 817 145 162 155 164 85 -293 -515 -196
output:
28
result:
ok single line: '28'
Test #8:
score: 0
Accepted
time: 62ms
memory: 4324kb
input:
16 342 -60 142 -165 356 -536 585 -429 528 256 723 691 691 910 353 -569 553 657 134 -269 411 354 512 -867 340 -724 348 -636 671 906 485 -303
output:
4
result:
ok single line: '4'
Test #9:
score: 0
Accepted
time: 60ms
memory: 4320kb
input:
16 -433 788 238 -612 -291 961 -381 -6 805 982 -761 252 -808 -265 602 253 -954 618 823 -420 687 270 -487 464 -789 651 468 -491 -303 462 259 -381
output:
5
result:
ok single line: '5'
Test #10:
score: 0
Accepted
time: 62ms
memory: 4252kb
input:
16 -560 823 -374 -972 116 555 934 443 -325 -972 -603 -803 -560 877 553 -565 901 443 -226 796 553 -473 -927 889 -927 957 126 555 -672 -803 -226 867
output:
12
result:
ok single line: '12'
Test #11:
score: 0
Accepted
time: 61ms
memory: 4260kb
input:
16 553 -473 -672 -803 116 555 553 -565 -374 -972 126 555 901 443 -560 877 -927 889 -226 867 -614 823 -832 788 -297 796 -603 -803 -374 -923 934 443
output:
5
result:
ok single line: '5'
Test #12:
score: 0
Accepted
time: 0ms
memory: 4112kb
input:
8 0 0 0 5 2 2 2 7 3 -2 5 0 4 -2 8 2
output:
6
result:
ok single line: '6'
Test #13:
score: 0
Accepted
time: 58ms
memory: 4320kb
input:
16 0 0 0 1 100 2 100 4 200 15 200 18 300 43 300 49 50 0 70 1 -123 -93 -122 -93 150 52 151 55 -571 -432 -570 -431
output:
7
result:
ok single line: '7'
Test #14:
score: 0
Accepted
time: 62ms
memory: 4320kb
input:
16 0 0 1 0 2 100 4 100 15 200 18 200 43 300 49 300 0 50 1 70 -93 -123 -93 -122 52 150 55 151 -432 -571 -431 -570
output:
7
result:
ok single line: '7'
Test #15:
score: 0
Accepted
time: 58ms
memory: 4360kb
input:
16 2 1 3 3 5 2 6 4 8 5 9 7 111 6 112 8 114 5 108 12 16 11 17 10 0 10 101 7 104 6 13 0
output:
7
result:
ok single line: '7'
Test #16:
score: 0
Accepted
time: 62ms
memory: 4328kb
input:
16 1 2 3 3 2 5 4 6 5 8 7 9 6 111 8 112 5 114 12 108 11 16 10 17 10 0 7 101 6 104 0 13
output:
7
result:
ok single line: '7'
Test #17:
score: 0
Accepted
time: 62ms
memory: 4324kb
input:
16 0 0 20 0 3 1 23 1 -3 3 12 16 16 6 7 7 27 7 10 8 30 8 25 11 2 12 1 14 11 116 5 118
output:
7
result:
ok single line: '7'
Test #18:
score: 0
Accepted
time: 63ms
memory: 4308kb
input:
16 0 0 20 0 3 1 23 1 -3 3 15 10 16 6 7 7 27 7 10 8 30 8 25 11 2 12 1 14 11 16 5 18
output:
11
result:
ok single line: '11'
Test #19:
score: 0
Accepted
time: 62ms
memory: 4376kb
input:
16 0 0 0 20 1 3 1 23 3 -3 10 15 6 16 7 7 7 27 8 10 8 30 11 25 12 2 14 1 16 11 18 5
output:
11
result:
ok single line: '11'
Test #20:
score: 0
Accepted
time: 62ms
memory: 4268kb
input:
16 0 0 0 20 1 3 1 23 3 -3 16 12 6 16 7 7 7 27 8 10 8 30 11 25 12 2 14 1 116 11 118 5
output:
7
result:
ok single line: '7'
Test #21:
score: 0
Accepted
time: 1ms
memory: 3880kb
input:
4 2 2 1 0 1 1 0 1
output:
0
result:
ok single line: '0'
Test #22:
score: 0
Accepted
time: 1ms
memory: 3936kb
input:
10 0 0 0 3 4 0 4 4 8 2 8 7 1 2 6 -2 9 3 10 9
output:
4
result:
ok single line: '4'
Test #23:
score: 0
Accepted
time: 1ms
memory: 3916kb
input:
10 0 0 3 0 0 4 4 4 2 8 7 8 2 1 -2 6 3 9 9 10
output:
4
result:
ok single line: '4'
Test #24:
score: 0
Accepted
time: 1ms
memory: 3944kb
input:
10 0 0 4 4 3 2 6 -1 7 5 8 2 4 0 8 9 9 3 0 4
output:
4
result:
ok single line: '4'
Test #25:
score: 0
Accepted
time: 0ms
memory: 3936kb
input:
10 0 0 4 4 2 3 -1 6 5 7 2 8 0 4 9 8 3 9 4 0
output:
4
result:
ok single line: '4'
Test #26:
score: 0
Accepted
time: 10ms
memory: 4044kb
input:
14 0 0 -2 2 5 -1 3 1 0 3 3 6 4 3 4 11 6 5 6 13 100 11 102 5 102 13 103 6
output:
11
result:
ok single line: '11'
Test #27:
score: 0
Accepted
time: 6ms
memory: 4268kb
input:
14 0 0 2 -2 -1 5 1 3 3 0 6 3 3 4 11 4 5 6 13 6 11 100 5 102 13 102 6 103
output:
11
result:
ok single line: '11'
Test #28:
score: 0
Accepted
time: 0ms
memory: 4040kb
input:
2 -1000 1000 1000 -1000
output:
0
result:
ok single line: '0'
Test #29:
score: 0
Accepted
time: 57ms
memory: 4312kb
input:
16 327 449 -509 761 -553 515 360 948 147 877 -694 468 241 320 463 -753 -206 -991 473 -738 -156 -916 -215 54 -112 -476 -452 780 -18 -335 -146 77
output:
12
result:
ok single line: '12'
Test #30:
score: 0
Accepted
time: 1ms
memory: 3964kb
input:
10 553 657 -39 -615 356 -536 587 759 411 354 342 147 675 918 512 -867 671 906 877 -794
output:
4
result:
ok single line: '4'
Test #31:
score: 0
Accepted
time: 2ms
memory: 3968kb
input:
12 356 -536 342 147 -39 -615 877 -794 411 354 587 759 628 897 671 906 553 657 675 918 512 -867 340 -724
output:
4
result:
ok single line: '4'
Test #32:
score: 0
Accepted
time: 9ms
memory: 4240kb
input:
14 553 657 342 147 356 -536 628 897 671 906 340 -724 -39 -615 877 -794 512 -867 587 759 411 354 108 485 -303 -57 675 918
output:
4
result:
ok single line: '4'