Advertisement
Guest User

Untitled

a guest
Nov 12th, 2019
250
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.65 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long LL;
  5. typedef pair<int, int> PII;
  6. typedef vector<int> VI;
  7. typedef vector<double> VD;
  8. #define MP make_pair
  9. #define PB push_back
  10. #define X first
  11. #define Y second
  12.  
  13. #define FOR(i, a, b) for(int i = (a); i < (b); ++i)
  14. #define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
  15. #define ITER(it, a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
  16. #define ALL(a) a.begin(), a.end()
  17. #define SZ(a) (int)((a).size())
  18. #define FILL(a, value) memset(a, value, sizeof(a))
  19. #define debug(a) cout << #a << " = " << a << endl;
  20.  
  21. const double PI = acos(-1.0);
  22. const LL INF = 1e9 + 47;
  23. const LL LINF = INF * INF;
  24. mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
  25.  
  26. inline bool isSquare(int s)
  27. {
  28. int t = sqrt(s);
  29. return t * t == s;
  30. }
  31.  
  32. const int N = 1000001;
  33. char dp[10][30][N + 30 * 81];
  34.  
  35. int f(int curr, int cnt, int sum)
  36. {
  37. if (curr == 10)
  38. return cnt == 0 && isSquare(sum);
  39.  
  40. if (dp[curr][cnt][sum] != -1)
  41. return dp[curr][cnt][sum];
  42.  
  43. int res = 0;
  44. FOR(i, 0, cnt + 1)
  45. res |= f(curr + 1, cnt - i, sum + i * curr * curr);
  46. return dp[curr][cnt][sum] = res;
  47. }
  48.  
  49. int main()
  50. {
  51. ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  52. //freopen("In.txt", "r", stdin);
  53. //freopen("In.txt", "w", stdout);
  54.  
  55. FILL(dp, -1);
  56. int mx = 0;
  57. FOR(i, 1, N)
  58. {
  59. int tut = -1;
  60. RFOR(j, i + 1, 0)
  61. if (f(2, i - j, j))
  62. {
  63. tut = i - j;
  64. break;
  65. }
  66.  
  67. assert(tut != -1);
  68. if (mx < tut)
  69. {
  70. cout << i << ',';
  71. mx = tut;
  72. }
  73. }
  74.  
  75. debug(mx);
  76. cerr << "Time elapsed: " << clock() / (double)CLOCKS_PER_SEC << endl;
  77. return 0;
  78. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement