結果

問題 No.1825 Except One
ユーザー qwewe
提出日時 2025-05-14 13:01:20
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 281 ms / 3,000 ms
コード長 5,329 bytes
コンパイル時間 760 ms
コンパイル使用メモリ 78,348 KB
実行使用メモリ 78,712 KB
最終ジャッジ日時 2025-05-14 13:03:15
合計ジャッジ時間 4,241 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 31
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>

using namespace std;

// Define constants based on problem constraints
const int MAX_N = 50;       // Maximum length of the sequence A
const int MAX_A = 100;      // Maximum value of an element in A
const int MAX_SUM = MAX_N * MAX_A; // Maximum possible sum of a subsequence (50 * 100 = 5000)

// DP table: dp[k][s][p] will store the count of subsequences of length k,
// with sum s, and maximum element value p.
// Dimensions are (N+1) x (MaxSum+1) x (MaxA+1).
// Use long long to prevent overflow as counts can be large.
long long dp[MAX_N + 1][MAX_SUM + 1][MAX_A + 1];

int main() {
    // Use faster I/O operations
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N; // Length of the sequence A
    cin >> N;

    vector<int> A(N); // Store the sequence A
    int overall_max_A = 0; // Track the maximum value present in the input array A
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
        overall_max_A = max(overall_max_A, A[i]); // Update overall maximum value seen
    }

    // Initialize DP table.
    // The base case is an empty subsequence: length 0, sum 0, max value 0.
    // Max value 0 is used as a placeholder; any non-empty subsequence with non-negative elements
    // will have a max value >= 0. This handles sequences containing 0 correctly.
    dp[0][0][0] = 1; 

    // Iterate through each element of the input sequence A
    for (int i = 0; i < N; ++i) {
        int curr_val = A[i]; // The current element being processed

        // Iterate downwards for k: length of subsequence *before* considering A[i].
        // The maximum length before considering A[i] (element at index i) is i.
        for (int k = i; k >= 0; --k) {
            
            // Iterate downwards for s: sum of subsequence *before* considering A[i].
            // A safe upper bound for the sum of k elements is k * MAX_A.
            int s_upper_bound = k * MAX_A; 
            for (int s = s_upper_bound; s >= 0; --s) {
                
                 // Iterate downwards for p: max value of subsequence *before* considering A[i].
                 // The maximum possible value an element can take is overall_max_A.
                for (int p = overall_max_A; p >= 0; --p) {
                    
                    // If the state dp[k][s][p] is reachable (count > 0)
                    if (dp[k][s][p] > 0) {
                        
                        // Consider forming a new subsequence by adding A[i]
                        int next_k = k + 1;             // New length is k+1
                        int next_s = s + curr_val;      // New sum is s + A[i]
                        // New maximum value is the maximum of the previous max p and the current value A[i]
                        int next_p = max(p, curr_val);
                        
                        // Check if the new sum is within the allowed bounds [0, MAX_SUM]
                        if (next_s <= MAX_SUM) {
                             // Increment the count for the new state (next_k, next_s, next_p)
                             // The += correctly aggregates counts if the same state can be reached in multiple ways.
                             dp[next_k][next_s][next_p] += dp[k][s][p];
                        }
                    }
                }
            }
        }
    }

    // After filling the DP table, calculate the total count of "good" subsequences
    long long total_good_subsequences = 0;

    // Iterate through all possible final states (k, s, p) recorded in the DP table
    // We only care about subsequences of length M >= 2, so k starts from 2.
    for (int k = 2; k <= N; ++k) { 
        
        // Iterate through possible sums. The maximum sum for a subsequence of length k is k * MAX_A.
        int s_final_upper_bound = k * MAX_A;
        for (int s = 0; s <= s_final_upper_bound; ++s) {
            
             // Iterate through possible maximum values. The max value cannot exceed overall_max_A.
            for (int p = 0; p <= overall_max_A; ++p) {
                
                // If this state (k, s, p) represents one or more subsequences
                if (dp[k][s][p] > 0) {
                    
                    // Check the conditions for a subsequence to be "good":
                    // 1. Length M = k must be >= 2. (Ensured by loop `k = 2` to `N`)
                    // 2. Sum S = s must be divisible by M-1 = k-1.
                    //    Since k >= 2, k-1 >= 1, so k-1 is always positive, division is safe.
                    if (s % (k - 1) == 0) {
                        // Calculate K = S / (M-1)
                        long long K_val = s / (k - 1); 
                        
                        // 3. K must be >= P = p (Maximum element in the subsequence)
                        if (K_val >= p) {
                            // If all conditions are met, this state corresponds to good subsequences.
                            // Add the count stored in dp[k][s][p] to the total.
                            total_good_subsequences += dp[k][s][p];
                        }
                    }
                }
            }
        }
    }

    // Output the final count
    cout << total_good_subsequences << endl;

    return 0;
}
0