Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- typedef long long LL;
- typedef pair<int, int> PII;
- typedef vector<int> VI;
- typedef vector<double> VD;
- #define MP make_pair
- #define PB push_back
- #define X first
- #define Y second
- #define FOR(i, a, b) for(int i = (a); i < (b); ++i)
- #define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
- #define ITER(it, a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
- #define ALL(a) a.begin(), a.end()
- #define SZ(a) (int)((a).size())
- #define FILL(a, value) memset(a, value, sizeof(a))
- #define debug(a) cout << #a << " = " << a << endl;
- const double PI = acos(-1.0);
- const LL INF = 1e9 + 47;
- const LL LINF = INF * INF;
- mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
- inline bool isSquare(int s)
- {
- int t = sqrt(s);
- return t * t == s;
- }
- const int N = 1000001;
- char dp[10][30][N + 30 * 81];
- int f(int curr, int cnt, int sum)
- {
- if (curr == 10)
- return cnt == 0 && isSquare(sum);
- if (dp[curr][cnt][sum] != -1)
- return dp[curr][cnt][sum];
- int res = 0;
- FOR(i, 0, cnt + 1)
- res |= f(curr + 1, cnt - i, sum + i * curr * curr);
- return dp[curr][cnt][sum] = res;
- }
- int main()
- {
- ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
- //freopen("In.txt", "r", stdin);
- //freopen("In.txt", "w", stdout);
- FILL(dp, -1);
- int mx = 0;
- FOR(i, 1, N)
- {
- int tut = -1;
- RFOR(j, i + 1, 0)
- if (f(2, i - j, j))
- {
- tut = i - j;
- break;
- }
- assert(tut != -1);
- if (mx < tut)
- {
- cout << i << ',';
- mx = tut;
- }
- }
- debug(mx);
- cerr << "Time elapsed: " << clock() / (double)CLOCKS_PER_SEC << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement