fork download
copy 
  1. /*
  2.     Fr: pdtduong
  3.     Note: uoc gi AC (")> 
  4.     Wish: HSGS/PTNK 26-27
  5. */
  6. #include<bits/stdc++.h>
  7. using namespace std;
  8. #define int long long
  9. #define endl "\n"
  10. #define lcm(a, b) a*b/__gcd(a, b)
  11. #define fi first
  12. #define se second
  13. #define pb push_back
  14. #define YES cout << "YES\n";
  15. #define NO cout << "NO\n";
  16. const int maxn = 1e6+5, INF = 1e18;
  17. int n, k;
  18. int a[maxn];
  19. int dp[1005], ndp[1005];
  20. signed main() {
  21.     ios_base::sync_with_stdio(false);
  22.     cin.tie(NULL);
  23.     // freopen("LED.INP", "r", stdin);
  24.     // freopen("LED.OUT", "w", stdout);
  25.     cin >> n >> k;
  26.     for(int i = 1; i <= n; i++) {
  27.     	cin >> a[i];
  28.     }
  29.     for(int r = 0; r < k; r++) {
  30.     	dp[r] = -INF;
  31.     }
  32.     dp[0] = 0;
  33.     for(int i = 1; i <= n; i++) {
  34.         for(int r = 0; r < k; r++) {
  35.         	ndp[r] = dp[r];
  36.         }
  37.         for(int r = 0; r < k; r++) {
  38.             if(dp[r] == -INF) {
  39.             	continue;
  40.             }
  41.             int nr = (r + a[i]) % k;
  42.             ndp[nr] = max(ndp[nr], dp[r] + a[i]);
  43.         }
  44.         for(int r = 0; r < k; r++) {
  45.         	dp[r] = ndp[r];
  46.         }
  47.     }
  48.     if(dp[0] >= k) {
  49.     	cout << dp[0];
  50.     } else {
  51.     	cout << 0;
  52.     }
  53.     return 0;
  54. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
3 6
10 2 4
stdout
copy 
12
https://ideone.com/LNCiln
language:
C++14 (gcc 8.3)
created:
2 days 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!