YEZAELP

PROG-1150: Pangpu

Jul 11th, 2020
80
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.77 KB | None
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using pii=pair<int,int>;
  4. int change(int i){
  5.     if(i<-30000) return i+60001;
  6.     if(i> 30000) return i-60001;
  7.     return i;
  8. }
  9. bool dp1[60001],dp2[60001];
  10. int main(){
  11.  
  12.     int n,mx=0;
  13.     scanf("%d",&n);
  14.     int ar[n+1];
  15.     for(int i=1;i<=n;i++) scanf("%d",&ar[i]);
  16.  
  17.     dp1[30000]=true;
  18.     for(int i=1;i<=n;i++){
  19.         for(int j=0;j<=60000;j++){
  20.             if(i%2==1) {
  21.                 dp2[j] = dp1[j] or dp1[change(j-ar[i]-30000)+30000];
  22.                 if(dp2[j]) mx=max(mx,j-30000);
  23.             }
  24.             else {
  25.                 dp1[j] = dp2[j] or dp2[change(j-ar[i]-30000)+30000];
  26.                 if(dp1[j]) mx=max(mx,j-30000);
  27.             }
  28.         }
  29.     }
  30.     printf("%d",mx);
  31.  
  32.  
  33.     return 0;
  34. }
RAW Paste Data Copied