QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#687517	#2177. Group Photo	liuziao^#	44	86ms	3736kb	C++23	1.0kb	2024-10-29 19:27:55	2024-10-29 19:27:58

Judging History

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

[2024-10-29 19:27:58]
评测

测评结果：44
用时：86ms
内存：3736kb

查看

[2024-10-29 19:27:55]
提交

answer

#include <bits/stdc++.h>

// #define int int64_t

const int kMaxN = 5e3 + 5;

int n;
int a[kMaxN], pos[kMaxN], f[kMaxN];

void dickdreamer() {
  std::cin >> n;
  for (int i = 1; i <= n; ++i) {
    std::cin >> a[i];
    pos[a[i]] = i;
  }
  memset(f, 0x3f, sizeof(f));
  f[0] = 0;
  for (int i = 1; i <= n; ++i) {
    for (int j = i; j; --j) {
      int cnt = 0;
      for (int k = 1; k < j; ++k)
        for (int s = j; s <= i; ++s)
          if (pos[k] > pos[s])
            ++cnt;
      for (int k = j; k <= i; ++k)
        for (int s = j; s < k; ++s)
          if (pos[k] > pos[s])
            ++cnt;
      f[i] = std::min(f[i], f[j - 1] + cnt);
    }
  }
  std::cout << f[n] << '\n';
}

int32_t main() {
#ifdef ORZXKR
  freopen("in.txt", "r", stdin);
  freopen("out.txt", "w", stdout);
#endif
  std::ios::sync_with_stdio(0), std::cin.tie(0), std::cout.tie(0);
  int T = 1;
  // std::cin >> T;
  while (T--) dickdreamer();
  // std::cerr << 1.0 * clock() / CLOCKS_PER_SEC << "s\n";
  return 0;
}

源文件, 语言: C++23

详细

Subtask #1:

score: 5

Accepted

Test #1:

score: 5

Accepted

time: 0ms

memory: 3680kb

input:

3
3 1 2

output:

result:

ok single line: '1'

Test #2:

score: 5

Accepted

time: 0ms

memory: 3612kb

input:

4
4 1 2 3

output:

result:

ok single line: '2'

Test #3:

score: 5

Accepted

time: 0ms

memory: 3724kb

input:

5
1 4 5 2 3

output:

result:

ok single line: '2'

Test #4:

score: 5

Accepted

time: 0ms

memory: 3676kb

input:

6
1 5 6 3 4 2

output:

result:

ok single line: '2'

Test #5:

score: 5

Accepted

time: 0ms

memory: 3728kb

input:

7
1 7 4 5 2 6 3

output:

result:

ok single line: '5'

Test #6:

score: 5

Accepted

time: 0ms

memory: 3664kb

input:

8
4 1 6 7 5 2 8 3

output:

result:

ok single line: '7'

Test #7:

score: 5

Accepted

time: 0ms

memory: 3668kb

input:

9
5 8 3 2 4 6 9 1 7

output:

result:

ok single line: '10'

Test #8:

score: 5

Accepted

time: 0ms

memory: 3676kb

input:

9
8 5 3 2 4 7 6 9 1

output:

result:

ok single line: '10'

Test #9:

score: 5

Accepted

time: 0ms

memory: 3608kb

input:

9
5 9 1 3 7 6 8 2 4

output:

result:

ok single line: '13'

Test #10:

score: 5

Accepted

time: 0ms

memory: 3664kb

input:

9
1 2 6 9 3 8 4 5 7

output:

result:

ok single line: '7'

Subtask #2:

score: 7

Accepted

Dependency #1:

100%

Accepted

Test #11:

score: 7

Accepted

time: 0ms

memory: 3672kb

input:

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

output:

result:

ok single line: '59'

Test #12:

score: 7

Accepted

time: 0ms

memory: 3604kb

input:

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

output:

result:

ok single line: '36'

Test #13:

score: 7

Accepted

time: 0ms

memory: 3612kb

input:

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

output:

result:

ok single line: '59'

Test #14:

score: 7

Accepted

time: 0ms

memory: 3604kb

input:

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

output:

result:

ok single line: '54'

Test #15:

score: 7

Accepted

time: 0ms

memory: 3664kb

input:

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

output:

result:

ok single line: '58'

Test #16:

score: 7

Accepted

time: 0ms

memory: 3612kb

input:

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

output:

result:

ok single line: '57'

Test #17:

score: 7

Accepted

time: 0ms

memory: 3608kb

input:

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

output:

result:

ok single line: '65'

Test #18:

score: 7

Accepted

time: 0ms

memory: 3668kb

input:

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

output:

result:

ok single line: '65'

Test #19:

score: 7

Accepted

time: 0ms

memory: 3616kb

input:

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

output:

result:

ok single line: '72'

Test #20:

score: 7

Accepted

time: 0ms

memory: 3680kb

input:

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

output:

result:

ok single line: '56'

Subtask #3:

score: 32

Accepted

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Test #21:

score: 32

Accepted

time: 82ms

memory: 3732kb

input:

198
184 48 40 52 7 79 49 34 17 24 120 11 69 128 44 19 154 167 191 72 20 144 163 150 168 183 188 122 108 194 127 75 171 21 187 18 116 91 169 82 165 124 57 87 92 106 181 30 170 186 135 118 175 189 159 123 125 14 102 39 66 149 161 114 110 23 117 113 70 67 84 129 111 131 90 2 143 93 46 197 179 55 56 174...

output:

result:

ok single line: '8437'

Test #22:

score: 32

Accepted

time: 83ms

memory: 3608kb

input:

199
130 170 159 43 49 37 66 100 183 89 99 199 76 119 154 90 177 54 8 5 120 112 41 135 136 88 26 132 178 150 145 117 71 158 64 62 52 95 53 45 56 187 74 168 131 11 47 113 20 3 38 194 29 124 125 142 12 182 127 1 188 84 180 61 63 111 27 58 42 70 14 110 79 193 122 36 19 25 138 153 80 72 139 133 118 4 189...

output:

result:

ok single line: '8335'

Test #23:

score: 32

Accepted

time: 84ms

memory: 3660kb

input:

199
69 120 84 19 44 54 125 51 155 153 6 98 88 63 132 91 146 162 32 5 60 76 28 167 18 92 3 1 131 31 137 21 169 17 24 59 43 168 102 164 122 15 127 22 126 34 89 39 161 53 72 36 139 23 192 171 114 142 86 50 176 160 154 112 128 65 48 74 144 172 100 196 80 27 71 64 185 187 189 10 121 195 133 165 108 113 1...

output:

result:

ok single line: '8261'

Test #24:

score: 32

Accepted

time: 85ms

memory: 3680kb

input:

200
144 19 60 123 120 93 95 178 69 171 158 200 85 159 33 143 74 3 125 5 24 110 188 57 88 197 182 105 160 126 82 154 192 86 10 59 187 54 23 135 111 199 107 174 87 183 131 121 114 194 77 198 113 50 89 172 102 193 122 140 94 73 92 41 100 139 101 129 141 109 151 2 130 27 173 133 177 155 115 136 76 62 15...

output:

result:

ok single line: '8691'

Test #25:

score: 32

Accepted

time: 86ms

memory: 3736kb

input:

200
12 42 25 40 48 149 54 189 139 67 49 75 174 9 21 98 135 17 186 141 78 20 200 81 123 129 44 64 11 153 105 36 158 159 101 151 43 39 142 194 157 134 3 175 127 191 35 109 167 7 148 188 132 169 131 168 27 50 113 145 184 70 29 173 45 2 8 33 128 163 162 183 51 133 63 180 108 190 6 106 171 196 177 26 76 ...

output:

result:

ok single line: '8675'

Test #26:

score: 32

Accepted

time: 85ms

memory: 3672kb

input:

200
141 89 9 150 139 166 50 134 158 130 39 189 122 62 70 8 101 69 143 83 127 48 164 200 125 184 79 142 120 99 174 171 177 56 94 195 51 47 87 118 85 116 198 182 187 28 33 78 123 91 21 106 154 19 98 129 20 110 157 52 75 5 1 46 165 43 81 88 36 80 170 92 22 193 53 163 34 128 180 24 117 159 95 59 25 172 ...

output:

result:

ok single line: '9026'

Test #27:

score: 32

Accepted

time: 85ms

memory: 3676kb

input:

200
87 31 106 17 65 61 169 134 80 45 155 24 92 191 114 164 6 44 39 1 41 154 183 77 33 5 117 120 30 71 150 179 176 60 43 107 130 173 69 174 98 51 56 63 54 70 168 89 194 74 123 131 46 110 172 97 185 101 196 32 25 116 121 170 187 193 163 16 7 4 132 152 105 75 189 171 136 29 161 141 13 86 188 165 34 103...

output:

result:

ok single line: '8815'

Test #28:

score: 32

Accepted

time: 81ms

memory: 3608kb

input:

200
31 159 197 200 143 156 93 71 58 54 46 107 96 125 108 182 150 78 28 109 174 128 37 165 2 126 68 13 196 162 38 76 67 61 180 198 106 137 25 15 56 19 169 44 8 52 154 16 49 53 39 119 114 59 175 167 4 36 193 35 185 82 60 62 1 42 151 135 177 192 184 30 168 132 3 110 43 50 102 115 153 187 124 120 133 73...

output:

result:

ok single line: '8346'

Test #29:

score: 32

Accepted

time: 85ms

memory: 3684kb

input:

200
187 120 160 171 37 157 107 106 30 172 168 124 58 155 145 45 138 169 122 102 109 93 133 7 182 86 129 88 95 148 5 2 200 159 131 16 114 164 39 112 98 184 126 134 198 176 41 188 27 150 99 89 65 59 74 179 101 52 173 91 141 153 67 92 196 42 116 177 195 33 142 22 113 128 175 165 23 35 103 104 90 80 162...

output:

result:

ok single line: '8260'

Test #30:

score: 32

Accepted

time: 85ms

memory: 3684kb

input:

200
24 65 188 38 101 170 111 150 160 79 48 36 130 105 189 96 61 191 182 17 91 133 85 81 94 25 126 198 121 176 11 118 87 2 10 166 154 148 109 179 117 180 88 99 161 62 68 142 57 97 102 151 34 19 12 168 37 41 114 200 49 16 43 159 64 20 152 80 75 7 14 146 108 163 156 71 9 167 162 184 172 90 155 196 190 ...

output:

result:

ok single line: '9084'

Subtask #4:

score: 0

Time Limit Exceeded

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted

Test #31:

score: 0

Time Limit Exceeded

input:

798
397 517 467 717 474 521 322 711 752 226 64 632 769 187 188 548 140 562 507 14 502 522 220 258 662 225 401 460 23 33 438 151 673 692 447 224 565 390 618 262 85 213 694 741 497 171 469 722 489 192 587 153 574 542 661 419 499 691 133 465 412 533 627 720 670 58 611 142 138 137 97 351 527 400 250 782...

output:

result:

Subtask #5:

score: 0

Skipped

Dependency #1:

100%

Accepted

Dependency #2:

100%

Accepted

Dependency #3:

100%

Accepted