Submission #1004435

---

Source Code Expand

#include <bits/stdc++.h>
      
#define FOR(i,a,b) for( ll i = (a); i < (ll)(b); i++ )
#define REP(i,n) FOR(i,0,n)
#define YYS(x,arr) for(auto& x:arr)
#define ALL(x) (x).begin(),(x).end()
#define SORT(x) sort( (x).begin(),(x).end() )
#define REVERSE(x) reverse( (x).begin(),(x).end() )
#define UNIQUE(x) (x).erase( unique( ALL( (x) ) ) , (x).end() )
#define PW(x) (1LL<<(x))
#define SZ(x) ((ll)(x).size())
#define SHOW(x) cout << #x << " = " << x << endl
     
#define pb emplace_back
#define fi first
#define se second
     
using namespace std;

typedef long double ld;
typedef long long int ll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<bool> vb;
typedef vector<ld> vd;
typedef vector<pi> vpi;
typedef vector<pl> vpl;
typedef vector<vpl> gr;
typedef vector<vl> ml;
typedef vector<vd> md;
typedef vector<vi> mi;
     
const ll INF = (ll)1e9 + 10;
const ll INFLL = (ll)1e18 + 10;
const ld EPS = 1e-12;
const ll MOD = 1e9+7;
     
template<class T> T &chmin( T &a , const T &b ){ return a = min(a,b); }
template<class T> T &chmax( T &a , const T &b ){ return a = max(a,b); }
template<class T> inline T sq( T a ){ return a * a; }

ll in(){ ll x; scanf( "%lld" , &x ); return x; }
char yuyushiki[1000010]; string stin(){ scanf( "%s" , yuyushiki ); return yuyushiki; }

// head

ll dp[2010][2010];

ll comb( ll a , ll b ){
  if( a > 2010 ){
    if( b == 0 || b == a ){
      return 1;
    } else if( b == 1 || b == a - 1 ){
      return a;
    } else if( b == 2 || b == a - 2 ){
      return min( INF , a * ( a - 1 ) / 2 );
    } else if( b == 3 ){
      return INF;
    } 
  }
  if( b < 0 or b > a ){
    return 0;
  }
  if( b == 0 or b == a ){
    return 1;
  }
  if( dp[a][b] != 0 ){
    return dp[a][b];
  }
  ll res = comb( a - 1 , b ) + comb( a - 1 , b - 1 );
  return dp[a][b] = min( res , INF );
}

int n, m;

pi calc( vi a , vi b ){
  assert( a <= b );

  int x = ( b[1] - a[1] ) / a[0];

  FOR( i , 1 , m ){
    ll cur = a[i];
    FOR( j , 1 , i+1 ){
      cur += a[i-j] * comb( x + j - 1 ,  j );
      chmin( cur , INFLL );
    }
    if( cur > b[i] ){
      return make_pair( x , false );
    }
    if( cur < b[i] ){
      return make_pair( x + 1 , false );
    }
  }
  
  return make_pair( x , true );
}

mi a;

int main(){

  n = in();
  m = in();
  a = mi( n , vi( m ) );
  REP( i , n ){
    REP( j , m ){
      a[i][j] = in();
    }
  }

  REP( i , n-1 ){
    if( a[i][0] > a[i+1][0] ){
      puts( "-1" );
      return 0;
    }
  }

  if( m == 1 ){
    puts( "0" );
    return 0;
  }

  ll cur = 0;
  ll ans = 0;
  REP( i , n-1 ){
    if( a[i][0] == a[i+1][0] ){
      if( a[i][1] < a[i+1][1] ){
	pi res = calc( a[i] , a[i+1] );
	cur = cur - res.fi + 1;
      } else if( a[i][1] > a[i+1][1] ){
	pi res = calc( a[i+1] , a[i] );
	if( res.se ){
	  cur = cur + res.fi + 1;
	} else {
	  cur = cur + res.fi;
	}
      } else {
	if( a[i] >= a[i+1] ){
	  cur++;
	}
      }
    } else {
      cur = 0;
    }
    chmax( cur , 0LL );
    ans += cur;
  }

  cout << ans << endl;
  
  return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘ll in()’:
./Main.cpp:44:36: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 ll in(){ ll x; scanf( "%lld" , &x ); return x; }
                                    ^
./Main.cpp: In function ‘std::string stin()’:
./Main.cpp:45:66: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
 char yuyushiki[1000010]; string stin(){ scanf( "%s" , yuyushiki ); return yuyushiki; }
                                                                  ^

Judge Result