fork download
copy 
  1. import java.util.*;
  2. public class Main {
  3.     public static void main(String args[]) {
  4.         Scanner sc = new Scanner(System.in);
  5.         int n = sc.nextInt();
  6.         int[] b = new int[n + 1];
  7.         int y = 0;
  8.         for (int i = 1; i <= n; i++) {
  9.             b[i] = sc.nextInt();
  10.             y = Math.max(y, b[i]);
  11.         }
  12.         long[][] dp = new long[n + 1][5001];
  13.         long[][] sumDP = new long[n + 1][5001];
  14.         dp[0][0] = 1;
  15.         for (int i = 1; i <= n; i++) {
  16.             dp[i][0] = 1;
  17.             for (int j = 1; j <= 5000; j++) {
  18.                 dp[i][j] = dp[i-1][j];
  19.                 sumDP[i][j] = sumDP[i-1][j];
  20.                 if (j - b[i] >= 0) {
  21.                     dp[i][j] += dp[i-1][j - b[i]];
  22.                     sumDP[i][j] += sumDP[i-1][j - b[i]] + (long)b[i]*dp[i-1][j - b[i]];
  23.                 }
  24.             }
  25.         }
  26.         long count = 0; 
  27.         long sum = 0;
  28.         for (int j = y; j <= 5000; j++) {
  29.             count += dp[n][j];
  30.             sum += sumDP[n][j];
  31.         }
  32.         System.out.println(count);
  33.         System.out.println(sum);
  34.     }
  35. }
  36.  
Success #stdin #stdout 0.2s 56640KB
comments (?)
stdin
copy 
7 
1 2 3 4 5 5 5
stdout
copy 
121
1583
https://ideone.com/K5mSL7
language:
Java (HotSpot 12)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!