Advertisement
Guest User

Untitled

a guest
Sep 18th, 2019
93
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 0.73 KB | None | 0 0
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long int
  5.  
  6. int arr[101][101],dp[101];
  7.  
  8. int main()
  9. {
  10. // freopen("f.txt","r",stdin);
  11. // freopen("g.txt","w",stdout);
  12. int n,gap,ans=-1;
  13. cin>>n;
  14. for(int i=1; i<=n; i++)
  15. {
  16. for(int j=1; j<=n; j++)
  17. {
  18. cin>>arr[i][j];
  19. arr[i][j]+=arr[i][j-1];
  20. }
  21. }
  22. for(int i=1;i<=n;i++)
  23. {
  24. for(int j=i;j<=n;j++)
  25. {
  26. for(int k=1;k<=n;k++)
  27. {
  28. gap=arr[k][j]-arr[k][i-1];
  29. dp[k]=max(gap+dp[k-1],gap);
  30. if(dp[k]>ans)
  31. ans=dp[k];
  32. }
  33. }
  34. }
  35. cout<<ans<<endl;
  36. return 0;
  37. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement