QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#723850 | #7704. Plus Minus Four Squares | MattTheNub# | AC ✓ | 9ms | 15552kb | C++23 | 2.6kb | 2024-11-08 01:28:13 | 2024-11-08 01:28:13 |
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] = 1;
if (q != 4)
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 && k != 3)
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
详细
Test #1:
score: 100
Accepted
time: 5ms
memory: 15420kb
input:
64
output:
12
result:
ok single line: '12'
Test #2:
score: 0
Accepted
time: 3ms
memory: 15432kb
input:
65
output:
10
result:
ok single line: '10'
Test #3:
score: 0
Accepted
time: 4ms
memory: 15352kb
input:
2023
output:
245
result:
ok single line: '245'
Test #4:
score: 0
Accepted
time: 4ms
memory: 15552kb
input:
0
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 9ms
memory: 15448kb
input:
5000
output:
951
result:
ok single line: '951'
Test #6:
score: 0
Accepted
time: 4ms
memory: 15416kb
input:
1024
output:
182
result:
ok single line: '182'
Test #7:
score: 0
Accepted
time: 8ms
memory: 15364kb
input:
2048
output:
355
result:
ok single line: '355'
Test #8:
score: 0
Accepted
time: 9ms
memory: 15348kb
input:
4096
output:
708
result:
ok single line: '708'
Test #9:
score: 0
Accepted
time: 8ms
memory: 15324kb
input:
1
output:
1
result:
ok single line: '1'
Test #10:
score: 0
Accepted
time: 9ms
memory: 15296kb
input:
2
output:
1
result:
ok single line: '1'
Test #11:
score: 0
Accepted
time: 8ms
memory: 15296kb
input:
4
output:
2
result:
ok single line: '2'
Test #12:
score: 0
Accepted
time: 9ms
memory: 15280kb
input:
3
output:
1
result:
ok single line: '1'
Test #13:
score: 0
Accepted
time: 8ms
memory: 15512kb
input:
1111
output:
131
result:
ok single line: '131'