QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#762615#8225. 最小值之和rizynvu0 2ms10444kbC++143.4kb2024-11-19 15:49:142024-11-19 15:49:19

Judging History

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

  • [2024-11-19 15:49:19]
  • 评测
  • 测评结果:0
  • 用时:2ms
  • 内存:10444kb
  • [2024-11-19 15:49:14]
  • 提交

answer

#include<bits/stdc++.h>
using ll = long long;
inline void fmax(ll &x, ll y) {
   x < y && (x = y);
}
inline void fmax(ll &x, ll y, int &xp, int yp) {
   x < y && (x = y, xp = yp);
}
inline int exgcd(int a, int b, ll &x, ll &y) {
   if (! b) {
      x = 1, y = 0;
      return a;
   }
   int g = exgcd(b, a % b, y, x);
   y -= 1ll * a / b * x;
   return g;
}
constexpr int maxn = 80 + 5;
int n;
ll a[maxn], mn[maxn][maxn], b[maxn];
ll f[maxn][maxn][maxn], h[maxn];
int fp[maxn][maxn][maxn];
void dfs(int l, int r, ll x) {
   if (l == r) return ;
   int len = r - l, z = x % len;
   ll y = f[l][r][z];
   assert(y >= x);
   for (int i = l; i < r; i++) {
      b[i] += (y - x) / (r - l);
   }
   dfs(l, fp[l][r][z], y), dfs(fp[l][r][z] + 1, r, y);
}
int main() {
   scanf("%d", &n);
   for (int i = 1; i <= n; i++) {
      scanf("%lld", &a[i]), mn[i][i] = a[i];
   }
   for (int i = 1; i <= n; i++) {
      for (int j = i + 1; j <= n; j++) {
         mn[i][j] = std::min(mn[i][j - 1], a[j]);
      }
   }
   if (n == 1) {
      puts(a[1] == 0 ? "Yes" : "No");
      return 0;
   }
   memset(f, -1, sizeof(f));
   for (int len = 1; len < n; len++) {
      for (int l = 1, r = len + 1; r <= n; l++, r++) {
         for (int p = l; p < r; p++) {
            int L = p - l, R = r - (p + 1);
            if (! L && ! R) {
               if (a[l] == a[r]) {
                  fmax(f[l][r][0], a[l], fp[l][r][0], p);
               }
            } else if (! L) {
               if (f[p + 1][r][a[l] % R] >= a[l]) {
                  fmax(f[l][r][a[l] % len], a[l], fp[l][r][a[l] % len], p);
               }  
            } else if (! R) {
               if (f[l][p][a[r] % L] >= a[r]) {
                  fmax(f[l][r][a[r] % len], a[r], fp[l][r][a[r] % len], p);
               }
            } else {
               ll x, y; int g = exgcd(L, R, x, y);
               y = -y;
               assert(x * L + y * -R == g);
               int z = L * R / g;
               memset(h, -1, sizeof(ll) * len);
               for (int a = 0; a < L; a++) {
                  for (int b = 0; b < R; b++) {
                     ll fl = f[l][p][a], fr = f[p + 1][r][b];
                     if (fl == -1 || fr == -1) continue;
                     if ((fl - fr) % g) continue;
                     ll val = (fl - fr) / g;
                     ll fx = x * val, fy = y * val;
                     fy = (fy % z + z) % z;
                     ll F = fr - fy * R;
                     if (F < 0) continue;
                     fmax(h[F % len], F);
                  }
               }
               for (int i = 0, ed = std::__gcd(z, len); i < ed; i++) {
                  for (int j = i, c = 0; c < 2; (j += len - z % len) %= len, c += j == i) {
                     fmax(h[(j + len - z % len) % len], h[j] - z);
                  }
               }
               for (int i = 0; i < len; i++) {
                  ll d = h[i] - mn[l][r];
                  if (d > 0) {
                     ll c = (d + z - 1) / z;
                     h[i] -= c * z;
                  }
                  fmax(f[l][r][i], h[i], fp[l][r][i], p);
               }
            }
         }
      }
   }
   if (f[1][n][0] == -1) {
      return puts("No"), 0;
   }
   puts("Yes");
   dfs(1, n, 0);
   for (int i = 1; i < n; i++) {
      printf("%lld ", b[i]);
   }
   return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 11
Accepted
time: 2ms
memory: 10304kb

input:

5
14 14 12 13 13

output:

Yes
5 3 3 4 

result:

ok The answer is correct.

Test #2:

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

input:

5
4 4 7 7 4

output:

Yes
1 1 4 1 

result:

ok The answer is correct.

Test #3:

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

input:

5
4 13 14 14 13

output:

Yes
1 4 5 4 

result:

ok The answer is correct.

Test #4:

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

input:

5
11 11 10 5 5

output:

Yes
5 4 1 2 

result:

ok The answer is correct.

Test #5:

score: 11
Accepted
time: 0ms
memory: 10212kb

input:

5
10 10 10 4 4

output:

Yes
4 4 1 1 

result:

ok The answer is correct.

Test #6:

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

input:

5
20 20 17 7 4

output:

Yes
10 7 2 1 

result:

ok The answer is correct.

Test #7:

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

input:

5
12 12 16 19 19

output:

Yes
3 3 5 8 

result:

ok The answer is correct.

Test #8:

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

input:

5
2 2 6 11 11

output:

Yes
0 0 2 7 

result:

wrong answer Your answer is wrong.

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%