SHARE
TWEET

Untitled

a guest Nov 12th, 2019 131 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  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. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top