QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#762567#8225. 最小值之和rizynvu0 0ms0kbC++143.1kb2024-11-19 15:32:552024-11-19 15:33:10

Judging History

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

  • [2024-11-19 15:33:10]
  • 评测
  • 测评结果:0
  • 用时:0ms
  • 内存:0kb
  • [2024-11-19 15:32:55]
  • 提交

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], 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 z = x % (r - l);
   ll y = f[l][r][z];
   for (int i = l; i <= r; i++) {
      y = std::min(y, (ll)a[i] / z * 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]);
   }
   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++) {
                  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
Runtime Error

Test #1:

score: 0
Runtime Error

input:

5
14 14 12 13 13

output:


result:


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%