Advertisement
pb_jiang

CF1829G WA

May 7th, 2023
151
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.47 KB | None | 0 0
  1. #include <assert.h>
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4.  
  5. template <class T> using mpq = priority_queue<T, vector<T>, greater<T>>;
  6.  
  7. using ll = long long;
  8. using pii = pair<int, int>;
  9. using pll = pair<ll, ll>;
  10. using vl = vector<ll>;
  11. using vi = vector<int>;
  12. using ul = unsigned long;
  13. using vul = vector<ul>;
  14.  
  15. vi layer;
  16.  
  17. pii get_rc(int a)
  18. {
  19.     int r = upper_bound(layer.begin(), layer.end(), a) - layer.begin() - 1;
  20.     int c = a - layer[r] + 1;
  21.     return {r, c};
  22. }
  23.  
  24. int main(int argc, char **argv)
  25. {
  26.     int t;
  27.     cin >> t;
  28.     vector<vul> dp(1 << 11, vul(1 << 11));
  29.     for (int i = 2023; i > 0; --i) {
  30.         for (int j = 1; j <= i; ++j) {
  31.             ul curr = i * (i - 1) / 2 + j;
  32.             dp[i][j] = dp[i + 1][j] + dp[i + 1][j + 1] - dp[i + 2][j + 1] + curr * curr;
  33.         }
  34.     }
  35.     // cerr << dp[1][1] << endl;
  36.     // assert(dp[1][1] == 286'0278'0236'2646'4826ul);
  37.  
  38.     layer = vi(1 << 11);
  39.     for (int i = 1; i <= 2023; ++i)
  40.         layer[i] = i * (i - 1) / 2 + 1;
  41.  
  42.     while (t--) {
  43.         int n;
  44.         cin >> n;
  45.         auto [r, c] = get_rc(n);
  46.         int r1 = r, c1 = c - 1;
  47.         int r2 = r, c2 = c + 1;
  48.         if (c1 >= 1)
  49.             r1 -= c1 - 1, c1 = 1;
  50.         else
  51.             c1 = c, r1 = r + 1;
  52.  
  53.         if (c2 <= r2)
  54.             r2 = c2;
  55.         else
  56.             r2 = r + 1;
  57.  
  58.         ll ans = dp[1][1] - dp[r1][c1] - dp[r2][c2] + dp[r + 2][c + 1];
  59.         cout << ans << endl;
  60.     }
  61.     return 0;
  62. };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement