• API
• FAQ
• Tools
• Archive
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;
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.

Top