Submission #1007211

---

Source Code Expand

#include <iostream>
#include <fstream>
#include <set>
#include <map>
#include <string>
#include <vector>
#include <bitset>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cassert>
#include <queue>

#define mp make_pair
#define pb push_back


typedef long long ll;
typedef long double ld;

using namespace std;
const ll INF = 2e9;
const int MAXN = 1200;

ll go[MAXN];
int n, m;
ll a[MAXN][MAXN];
ll x[MAXN];

ll cnk(ll n, ll k) {
	ll fc = 1;
	for (int j = 1; j <= k; ++j)
		fc *= j;
	ll ans = 1;
	for (ll j = n; j > n - k; --j) {
		ans *= j;
		if (ans >= fc * INF)
			return INF;
	}
	return ans / fc;
}



int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			scanf("%lld", &a[i][j]);
	for (int i = 0; i < n - 1; ++i) {
		if (a[i][0] > a[i + 1][0] || (m == 1 && a[i][0] == a[i + 1][0])) {
			cout << -1 << "\n";
			return 0;
		}
		int fl = 0;
		for (int j = 0; j < m; ++j) {
			if (a[i][j] < a[i + 1][j]) {
				fl = 1;
				break;
			}
			if (a[i][j] < a[i + 1][j]) {
				fl = -1;
				break;
			}
		}
		if (fl == 0) {
			go[i] = 1;
		}
		else if (fl == 1) {
			if (a[i][0] < a[i + 1][0]) {
				continue;
			}
			ll nd = (a[i + 1][1] - a[i][1] + a[i][0] - 1) / a[i][0];
			for (int j = 0; j < m; ++j)
				x[j] = a[i][j];
			if (nd <= 100) {
				for (int it = 0; it < nd; ++it) {
					ll sum = 0;
					for (int j = 0; j < m; ++j) {
						sum = min(INF, sum + x[j]);
						x[j] = sum;
					}
				}
			}
			else {
				for (int j = 10; j < m; ++j)
					x[j] = INF;
				for (int j = min(9, m - 1); j >= 1; --j) {
					for (int k = 0; k < j; ++k)
						x[j] = min(INF, x[j] + cnk(nd - 1 + j - k, j - k) * x[k]);
				}
			}
			int fl2 = 0;
			for (int j = 0; j < m; ++j) {
				if (x[j] < a[i + 1][j]) {
					fl2 = 1;
					break;
				}
				if (x[j] > a[i + 1][j])
					break;
			}
			if (fl2)
				go[i] = -nd;
			else
				go[i] = -(nd - 1);
		}
		else {
			ll nd = (a[i][1] - a[i + 1][1] + a[i + 1][0] - 1) / a[i + 1][0];
			for (int j = 0; j < m; ++j)
				x[j] = a[i + 1][j];
			if (nd <= 100) {
				for (int it = 0; it < nd; ++it) {
					ll sum = 0;
					for (int j = 0; j < m; ++j) {
						sum = min(INF, sum + x[j]);
						x[j] = sum;
					}
				}
			}
			else {
				for (int j = 10; j < m; ++j)
					x[j] = INF;
				for (int j = min(m - 1, 9); j >= 1; --j) {
					for (int k = 0; k < j; ++k)
						x[j] = min(INF, x[j] + cnk(nd - 1 + j - k, j - k) * x[k]);
				}
			}
			int fl2 = 0;
			for (int j = 0; j < m; ++j) {
				if (x[j] < a[i][j])
					break;
				if (x[j] > a[i][j]) {
					fl2 = 1;
					break;
				}
			}
			if (fl2)
				go[i] = nd;
			else
				go[i] = nd + 1;
		}
	}
	ll ans = 0;
	ll now = 0;
	for (int i = 1; i < n; ++i) {
		if (a[i][0] > a[i - 1][0]) {
			now = 0;
			continue;
		}
		ll gg = max(0ll, now + go[i - 1]);
		ans += gg;
		now = gg;
	}
	cout << ans << "\n";
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:47:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
                       ^
./Main.cpp:50:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    scanf("%lld", &a[i][j]);
                           ^

Judge Result