QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#723839 | #7704. Plus Minus Four Squares | MattTheNub# | WA | 8ms | 15504kb | C++23 | 2.6kb | 2024-11-08 01:20:24 | 2024-11-08 01:20:24 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T> using v = vector<T>;
using ll = long long;
using dd = long double;
using int2 = pair<int, int>;
using ll2 = pair<ll, ll>;
using dd2 = pair<dd, dd>;
#define f first
#define s second
#define all(x) begin(x), end(x)
istream &__cin = cin;
#ifdef DEV_MODE
#include "debug.h"
__cinwrapper __cin_wrapper;
#define cin __cin_wrapper
#else
#define dbg(...)
#define dbg2d(...)
#endif
template <class T1, class T2>
istream &operator>>(istream &in, pair<T1, T2> &p) {
in >> p.first >> p.second;
return in;
}
template <class T> istream &operator>>(istream &in, v<T> &v) {
for (auto &x : v)
in >> x;
return in;
}
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
/*
_______________________________________
( If you don't fail at least 90% of the )
( time, you're not aiming high enough. )
( )
( - Alan Kay )
---------------------------------------
o ^__^
o (oo)\_______
(__)\ )\/\
||----w |
|| ||
*/
const bool INTERACTIVE = false;
const bool MULTITEST = false;
/******************************************************************************/
#pragma region templates
#pragma endregion templates
int dp[76][10001][4]{0};
void solve() {
int n;
cin >> n;
for (int i = 0; i * i <= 5000; i++) {
for (int q = 1; q <= 4 && q * i * i <= 5000; q++)
dp[i][5000 - q * i * i][q - 1] = dp[i][5000 + q * i * i][q - 1] = 1;
}
for (int i = 1; i <= 75; i++) {
for (int j = 0; j <= 1e4; j++) {
dp[i][j][0] += dp[i - 1][j][0];
}
}
for (int i = 1; i <= 75; i++) {
for (int j = 0; j <= 1e4; j++) {
for (int k = 1; k < 4; k++) {
for (int q = 1; q <= k; q++) {
if (j - q * i * i >= 0)
dp[i][j][k] += dp[i - 1][j - q * i * i][k - q];
if (j + q * i * i <= 1e4)
dp[i][j][k] += dp[i - 1][j + q * i * i][k - q];
}
dp[i][j][k] += dp[i - 1][j][k];
}
}
}
cout << dp[(int)sqrt(n)][5000 + n][3];
}
int main() {
#ifdef DEV_MODE
debug_start(INTERACTIVE, "k.txt");
#else
ios::sync_with_stdio(false);
cin.tie(nullptr);
#endif
int t;
if (MULTITEST)
cin >> t;
else
t = 1;
while (t--)
solve();
#ifdef DEV_MODE
debug_exit(INTERACTIVE);
#endif
}
#ifdef DEV_MODE
#include "debug.cpp"
#endif
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 8ms
memory: 15504kb
input:
64
output:
12
result:
ok single line: '12'
Test #2:
score: 0
Accepted
time: 8ms
memory: 15480kb
input:
65
output:
10
result:
ok single line: '10'
Test #3:
score: -100
Wrong Answer
time: 4ms
memory: 15396kb
input:
2023
output:
246
result:
wrong answer 1st lines differ - expected: '245', found: '246'