QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#352204#8225. 最小值之和yaoxi_std26 25ms51092kbC++143.5kb2024-03-12 23:28:202024-03-12 23:28:21

Judging History

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

  • [2024-03-12 23:28:21]
  • 评测
  • 测评结果:26
  • 用时:25ms
  • 内存:51092kb
  • [2024-03-12 23:28:20]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
#define debug(fmt, ...) \
  fprintf(stderr, "[%d] " fmt "\n", __LINE__, ##__VA_ARGS__)
template <class _Tx, class _Ty>
inline void chkmin(_Tx& x, const _Ty& y) { if (y < x) x = y; }
template <class _Tx, class _Ty>
inline void chkmax(_Tx& x, const _Ty& y) { if (x < y) x = y; }
bool Mbe;
using ll = long long;
constexpr int N = 55;
constexpr ll infll = 1e15;
int n;
ll a[N];
ll div_c(ll n, ll d) {
  return n >= 0 ? (n + d - 1) / d : n / d;
}
struct dat {
  ll val;
  int pre;
  bool operator<(const dat& rhs) const { return val < rhs.val; }
} dp[N][N][N][N];
bool Med;
int main() {
  // debug("Mem: %.4lfMB.", fabs(&Med - &Mbe) / 1048576);
  cin.tie(0)->sync_with_stdio(0);
  cin >> n, --n;
  for (int i = 0; i <= n; ++i) cin >> a[i];
  if (!n) return cout << (!a[0] ? "Yes" : "No") << '\n', 0;
  for (int k = 1; k <= n; ++k) {
    for (int l = 1, r = k; r <= n; ++l, ++r) {
      ll vl = a[l - 1], vr = a[r];
      if (k == 1) {
        if (vl == vr) {
          dp[l][r][k][0] = {-vl, l};
        } else {
          dp[l][r][k][0] = {1, -1};
        }
      } else {
        for (int i = 0; i < k; ++i) dp[l][r][k][i] = {k + i, -1};
        for (int p = l; p <= r; ++p) {
          for (int i = 0; i < k; ++i) {
            ll val = 0;
            if (p == l) {
              val = dp[p + 1][r][k][i].val;
              if (val < -vl) val += k * div_c(-vl - val, k);
              if (val != -vl) continue;
            } else if (p == r) {
              val = dp[l][p - 1][k][i].val;
              if (val < -vr) val += k * div_c(-vr - val, k);
              if (val != -vr) continue;
            } else {
              val = max(dp[l][p - 1][k][i].val, dp[p + 1][r][k][i].val);
            }
            chkmin(dp[l][r][k][i], dat{val, p});
          }
        }
      }
      for (int tk = k + 1; tk <= n; ++tk) {
        for (int i = 0; i < tk; ++i) dp[l][r][tk][i] = {tk + i, -1};
        for (int i = 0; i < k; ++i) {
          int p = dp[l][r][k][i].val % tk;
          if (p < 0) p += tk;
          chkmin(dp[l][r][tk][p], dat{dp[l][r][k][i].val, i});
        }
        int gd = __gcd(k, tk);
        for (int i = 0; i < gd; ++i) {
          for (int j = 0, p = i; j < tk / gd * 2; ++j, p = (p + k) % tk) {
            chkmin(dp[l][r][tk][(p + k) % tk], dat{dp[l][r][tk][p].val + k, dp[l][r][tk][p].pre});
          }
        }
      }
    }
  }
  if (dp[1][n][n][0].val > 0) return cout << "No\n", 0;
  cout << "Yes\n";
  function<void(int, int, int, int, ll, ll)> print =
      [&](int l, int r, int k, int t, ll mn, ll cur) {
    if (l > r) return;
    int tk = r - l + 1;
    if (k != tk) {
      int p = dp[l][r][k][t].pre;
      print(l, r, tk, p, mn + (dp[l][r][k][t].val - dp[l][r][tk][p].val) / tk, cur);
      return;
    }
    if (l == r) {
      cout << a[r] - cur << " \n"[l == n];
      return;
    }
    int p = dp[l][r][k][t].pre;
    mn = (-cur - dp[l][r][k][t].val) / k;
    if (l < p) {
      print(l, p - 1, k, t,
            mn + (dp[l][r][k][t].val - dp[l][p - 1][k][t].val) / k,
            cur + (r - p + 1) * mn);
    }
    cout << mn << " \n"[p == n];
    if (p < r) {
      print(p + 1, r, k, t,
            mn + (dp[l][r][k][t].val - dp[p + 1][r][k][t].val) / k,
            cur + (p - l + 1) * mn);
    }
  };
  print(1, n, n, 0, 0, 0);
  return 0;
}
/*
g++ -std=c++14 -O2 -o QOJ8225 QOJ8225.cpp
-Wall -Wextra -Wshadow
-fsanitize=address,undefined -g
*/

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 11
Accepted

Test #1:

score: 11
Accepted
time: 1ms
memory: 11736kb

input:

5
14 14 12 13 13

output:

Yes
5 3 3 4

result:

ok The answer is correct.

Test #2:

score: 0
Accepted
time: 2ms
memory: 11692kb

input:

5
4 4 7 7 4

output:

Yes
1 1 4 1

result:

ok The answer is correct.

Test #3:

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

input:

5
4 13 14 14 13

output:

Yes
1 4 5 4

result:

ok The answer is correct.

Test #4:

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

input:

5
11 11 10 5 5

output:

Yes
5 4 1 2

result:

ok The answer is correct.

Test #5:

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

input:

5
10 10 10 4 4

output:

Yes
4 4 1 1

result:

ok The answer is correct.

Test #6:

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

input:

5
20 20 17 7 4

output:

Yes
10 7 2 1

result:

ok The answer is correct.

Test #7:

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

input:

5
12 12 16 19 19

output:

Yes
3 3 5 8

result:

ok The answer is correct.

Test #8:

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

input:

5
2 2 6 11 11

output:

Yes
2 0 3 8

result:

ok The answer is correct.

Test #9:

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

input:

5
10 10 8 5 5

output:

Yes
5 3 1 2

result:

ok The answer is correct.

Test #10:

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

input:

5
24 24 28 28 26

output:

Yes
6 6 9 7

result:

ok The answer is correct.

Test #11:

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

input:

5
5 5 22 31 31

output:

Yes
2 1 10 19

result:

ok The answer is correct.

Test #12:

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

input:

5
8 33 38 38 29

output:

Yes
2 11 16 9

result:

ok The answer is correct.

Test #13:

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

input:

5
16 16 4 12 12

output:

Yes
13 1 1 9

result:

ok The answer is correct.

Test #14:

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

input:

5
29 29 24 26 26

output:

Yes
11 6 6 8

result:

ok The answer is correct.

Test #15:

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

input:

5
0 33 33 32 32

output:

Yes
0 13 10 12

result:

ok The answer is correct.

Test #16:

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

input:

5
20 16 8 25 22

output:

No

result:

ok The answer is correct.

Test #17:

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

input:

5
0 2 3 0 2

output:

No

result:

ok The answer is correct.

Test #18:

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

input:

5
28 23 29 29 24

output:

No

result:

ok The answer is correct.

Test #19:

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

input:

5
0 1 0 4 2

output:

No

result:

ok The answer is correct.

Test #20:

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

input:

5
12 21 21 13 4

output:

No

result:

ok The answer is correct.

Test #21:

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

input:

5
9 22 25 23 12

output:

No

result:

ok The answer is correct.

Test #22:

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

input:

5
6 7 7 6 6

output:

Yes
2 3 1 3

result:

ok The answer is correct.

Test #23:

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

input:

5
25 25 24 20 20

output:

Yes
8 7 5 5

result:

ok The answer is correct.

Test #24:

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

input:

5
17 9 8 16 9

output:

No

result:

ok The answer is correct.

Test #25:

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

input:

5
20 5 34 34 23

output:

No

result:

ok The answer is correct.

Test #26:

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

input:

5
15 33 35 35 31

output:

No

result:

ok The answer is correct.

Test #27:

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

input:

5
21 22 23 1 18

output:

No

result:

ok The answer is correct.

Test #28:

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

input:

5
4 2 3 4 2

output:

No

result:

ok The answer is correct.

Test #29:

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

input:

5
16 25 8 19 7

output:

No

result:

ok The answer is correct.

Test #30:

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

input:

5
4 0 8 6 6

output:

No

result:

ok The answer is correct.

Test #31:

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

input:

2
2 3

output:

No

result:

ok The answer is correct.

Test #32:

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

input:

2
2 2

output:

Yes
2

result:

ok The answer is correct.

Test #33:

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

input:

1
0

output:

Yes

result:

ok The answer is correct.

Test #34:

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

input:

1
233

output:

No

result:

ok The answer is correct.

Subtask #2:

score: 15
Accepted

Dependency #1:

100%
Accepted

Test #35:

score: 15
Accepted
time: 0ms
memory: 17940kb

input:

8
16 16 8 8 9 9 6 6

output:

Yes
16 0 4 1 5 1 2

result:

ok The answer is correct.

Test #36:

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

input:

8
16 16 9 21 21 23 23 23

output:

Yes
10 1 2 14 1 9 9

result:

ok The answer is correct.

Test #37:

score: 0
Accepted
time: 2ms
memory: 17868kb

input:

8
10 10 15 15 15 10 10 5

output:

Yes
10 0 6 6 1 6 1

result:

ok The answer is correct.

Test #38:

score: 0
Accepted
time: 2ms
memory: 20220kb

input:

8
13 13 15 15 24 24 24 10

output:

Yes
7 1 9 1 9 9 2

result:

ok The answer is correct.

Test #39:

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

input:

8
5 13 16 25 25 24 4 4

output:

Yes
1 3 4 9 8 0 4

result:

ok The answer is correct.

Test #40:

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

input:

8
1313 1695 1695 1129 1129 711 557 557

output:

Yes
459 841 79 575 157 80 80

result:

ok The answer is correct.

Test #41:

score: 0
Accepted
time: 3ms
memory: 17892kb

input:

8
1386 1416 1416 1069 1069 390 645 645

output:

Yes
554 584 56 735 56 55 315

result:

ok The answer is correct.

Test #42:

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

input:

8
3377 3377 3164 3164 3570 3570 3365 3365

output:

Yes
665 452 452 452 726 518 521

result:

ok The answer is correct.

Test #43:

score: 0
Accepted
time: 2ms
memory: 18176kb

input:

8
28167709 33181201 33829300 33829300 21924091 26145199 28398185 28398185

output:

Yes
5213219 7719965 8368064 3132013 3132013 5242567 7495553

result:

ok The answer is correct.

Test #44:

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

input:

8
4726918 12793592 12793592 6681214 13995142 22020836 22566624 22566624

output:

Yes
675274 7113378 1000988 1000991 3438967 7451814 7997602

result:

ok The answer is correct.

Test #45:

score: 0
Accepted
time: 2ms
memory: 17904kb

input:

8
9146297 15736298 15736298 16471005 16471005 14187656 14187656 6001415

output:

Yes
2429786 9019787 857345 11326935 857345 9043586 857345

result:

ok The answer is correct.

Test #46:

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

input:

8
25115296 25115296 22120670 21035156 20603135 28703897 28703897 27553199

output:

Yes
6624695 3630069 3087312 2943305 2943305 7569035 6418337

result:

ok The answer is correct.

Test #47:

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

input:

8
22440147 22440147 22626721 22626721 22592252 22592252 19174074 19174074

output:

Yes
6005229 2739153 6191803 2739153 6157332 2739154 2739154

result:

ok The answer is correct.

Test #48:

score: 0
Accepted
time: 2ms
memory: 17956kb

input:

8
12 0 13 8 18 18 18 0

output:

No

result:

ok The answer is correct.

Test #49:

score: 0
Accepted
time: 2ms
memory: 17904kb

input:

8
3 23 13 18 26 12 25 25

output:

No

result:

ok The answer is correct.

Test #50:

score: 0
Accepted
time: 2ms
memory: 17940kb

input:

8
1353255 1004808 981534 1400692 1246708 409750 1177255 1177255

output:

No

result:

ok The answer is correct.

Test #51:

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

input:

8
96 96 99 99 4 94 39 36

output:

No

result:

ok The answer is correct.

Test #52:

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

input:

8
15 21 0 20 20 15 13 6

output:

No

result:

ok The answer is correct.

Test #53:

score: 0
Accepted
time: 2ms
memory: 19928kb

input:

8
2 1 0 2 6 6 5 1

output:

No

result:

ok The answer is correct.

Test #54:

score: 0
Accepted
time: 2ms
memory: 19884kb

input:

8
7 12 11 11 1 11 4 11

output:

No

result:

ok The answer is correct.

Test #55:

score: 0
Accepted
time: 2ms
memory: 18168kb

input:

8
18 3 27 27 19 10 6 6

output:

No

result:

ok The answer is correct.

Subtask #3:

score: 0
Wrong Answer

Dependency #2:

100%
Accepted

Test #56:

score: 0
Wrong Answer
time: 0ms
memory: 22188kb

input:

14
10 10 2 30 45 50 50 47 47 47 46 33 33 32

output:

Yes
9 1 0 4 9 14 11 2 15 13 3 8 6

result:

wrong answer Your answer is wrong.

Subtask #4:

score: 0
Wrong Answer

Dependency #1:

100%
Accepted

Test #77:

score: 25
Accepted
time: 25ms
memory: 40672kb

input:

49
28 28 28 24 37 37 33 36 36 29 43 43 41 41 29 48 51 51 44 49 50 50 9 9 15 18 18 3 17 17 9 13 17 17 13 13 0 6 6 16 21 25 25 19 7 19 19 17 4

output:

Yes
14 14 0 12 25 0 9 12 5 7 21 0 41 0 5 12 15 10 3 17 18 0 9 0 7 10 1 0 17 0 3 5 9 0 13 0 0 6 0 4 6 10 5 0 2 9 7 1

result:

ok The answer is correct.

Test #78:

score: -25
Wrong Answer
time: 20ms
memory: 51092kb

input:

49
3 3 29 29 31 31 34 34 34 34 31 22 22 21 21 21 36 36 37 42 42 41 22 22 6 6 19 37 65 71 71 77 78 78 76 76 42 46 46 40 60 60 60 60 60 60 6 6 4

output:

Yes
3 0 29 0 31 0 34 0 14 11 3 7 6 0 21 0 36 0 9 13 12 4 6 0 6 0 4 10 24 30 1 36 37 0 76 0 21 25 0 20 40 0 60 0 57 1 3 1

result:

wrong answer Your answer is wrong.

Subtask #5:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

100%
Accepted

Dependency #2:

100%
Accepted

Dependency #3:

0%