Submission #141279

#	Time	Username	Problem	Language	Result	Execution time	Memory
141279		meatrow	Toys (CEOI18_toy)	C++17	100 / 100	3458 ms	86804 KiB

toy

//#pragma GCC optimize("O3")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,tune=native")
//#pragma GCC optimize ("unroll-loops")
#include <bits/stdc++.h>

using namespace std;

using ll = long long;
using ld = long double;

const int N = 2000;

set<int> dp[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
    vector<int> divs;
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            divs.push_back(i);
            if (i != n / i) {
                divs.push_back(n / i);
            }
        }
    }
    sort(divs.begin(), divs.end());
    for (int i = 0; i < divs.size(); i++) {
        dp[i].insert(divs[i] - 1);
        for (int j = 0; j < i; j++) {
            if (divs[i] % divs[j] == 0) {
                for (int a : dp[j]) {
                    dp[i].insert(a + divs[i] / divs[j] - 1);
                }
            }
        }
    }
    cout << dp[divs.size() - 1].size() << '\n';
    for (int a : dp[divs.size() - 1]) {
        cout << a << ' ';
    }
    return 0;
}

Compilation message (stderr)

toy.cpp: In function 'int main()':
toy.cpp:31:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < divs.size(); i++) {
                     ~~^~~~~~~~~~~~~

• Subtask 1: 19 / 19
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 20 / 20
• Subtask 5: 21 / 21