QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#546595#7704. Plus Minus Four SquaresOlegpresnyakov#AC ✓38ms3648kbC++171.3kb2024-09-04 10:00:482024-09-04 10:00:50

Judging History

你现在查看的是最新测评结果

  • [2024-09-04 10:00:50]
  • 评测
  • 测评结果:AC
  • 用时:38ms
  • 内存:3648kb
  • [2024-09-04 10:00:48]
  • 提交

answer

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <algorithm>
#include <set>
#include <map>
#include <fstream>
#include <time.h>
#include <unordered_map>
#include <cstdlib>
#include <string.h>
#include <bitset>
#include <unordered_set>
#include <cstdlib>
#include <string.h>
#include <cassert>
#define all(a) (a).begin(), (a).end()
#define int long long
using namespace std;

vector<int> sq;
int glob = 0;
void dfs(int n, int sum, int index, int step, int prelast, int last){
    if(step == 4){
        return;
    }

    if(prelast != last){
        index--;
    }

    for(int i = index; i >= 1; --i){
        int new_el = sum - last * sq[i];
        //cerr << new_el << "\n";
        if(sum - last * sq[i] == n){
            glob++;
        }

        dfs(n, new_el, i, step + 1, last, -1);
        dfs(n, new_el, i, step + 1, last, 1);
    }
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n;
    cin >> n;
    sq.clear();

    for(int i = 0; i * i <= n; ++i){
        sq.push_back(i * i);
    }

    if(n == 0){
        cout << "1\n";
        return 0;
    }

    dfs(n, 0, sq.size() - 1, 0, -1, -1);
    cout << glob << "\n";
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3608kb

input:

64

output:

12

result:

ok single line: '12'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3644kb

input:

65

output:

10

result:

ok single line: '10'

Test #3:

score: 0
Accepted
time: 3ms
memory: 3632kb

input:

2023

output:

245

result:

ok single line: '245'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3552kb

input:

0

output:

1

result:

ok single line: '1'

Test #5:

score: 0
Accepted
time: 38ms
memory: 3552kb

input:

5000

output:

951

result:

ok single line: '951'

Test #6:

score: 0
Accepted
time: 2ms
memory: 3580kb

input:

1024

output:

182

result:

ok single line: '182'

Test #7:

score: 0
Accepted
time: 7ms
memory: 3644kb

input:

2048

output:

355

result:

ok single line: '355'

Test #8:

score: 0
Accepted
time: 27ms
memory: 3624kb

input:

4096

output:

708

result:

ok single line: '708'

Test #9:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

1

output:

1

result:

ok single line: '1'

Test #10:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

2

output:

1

result:

ok single line: '1'

Test #11:

score: 0
Accepted
time: 0ms
memory: 3624kb

input:

4

output:

2

result:

ok single line: '2'

Test #12:

score: 0
Accepted
time: 0ms
memory: 3632kb

input:

3

output:

1

result:

ok single line: '1'

Test #13:

score: 0
Accepted
time: 2ms
memory: 3648kb

input:

1111

output:

131

result:

ok single line: '131'