fork download 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define fi first
  5. #define se second
  6. #define MOD 1000000007
  7. #define FOR(i,a,b) for (int i = (a);i <= (b);i++)
  8. #define FOD(i,a,b) for (int i = (b);i >= (a);i--)
  9. #define ALL(x) (x).begin(),(x).end()
  10. #define ii pair<ll,int>
  11. #define iii pair<ll,pair<ll,int>>
  12. //const int MOD = 998244353;
  13. const int MAXN = 1e3 + 7;
  14. const int maxn = 1e6 + 6;
  15. int a[MAXN][MAXN];
  16. ll cost[maxn],dp[MAXN][MAXN];
  17. int main(){
  18.     ios_base::sync_with_stdio(false);
  19.     cin.tie(0); cout.tie(0);
  20.     //freopen("cardscore.inp","r",stdin);
  21.     //freopen("cardscore.out","w",stdout);
  22.     int n,m;cin >> n >> m;
  23.     FOR(i,1,n){
  24.         FOR(j,1,m)cin >> a[i][j];
  25.     }
  26.     int l = 1e9;
  27.     FOR(i,1,n)
  28.     FOR(j,1,m)l = min(l,a[i][j]);
  29.     int r = l + (int)1e6;
  30.     int mx = 0;
  31.     FOR(i,1,(int)sqrt(r)){
  32.         if (i >= l)cost[i - l] = cost[i - l] - i;
  33.         for (int j = l + (i - l % i) % i;j <= r;j+=i){            
  34.             cost[j - l] = cost[j - l] + i;
  35.             if (j / i != i && i / j > (int)sqrt(r))cost[j - l] = cost[j - l] + j / i;
  36.         }
  37.     }
  38.     ll ans = 1e18;
  39.     memset(dp,0x3f,sizeof(dp));
  40.     dp[1][0] = 0;
  41.     FOR(i,1,n){
  42.         FOR(j,1,m)dp[i][j] = min(dp[i - 1][j],dp[i][j - 1]) + cost[a[i][j] - l];
  43.     }
  44.     cout << dp[n][m];
  45.     return 0^0;
  46. }
Success #stdin #stdout 0.1s 20776KB
comments (?)
stdin 
1 3
1000 1001 1007
stdout 
1756
https://ideone.com/YAXvLV
language:
C++ (gcc 8.3)
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!