제출 #62740

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
62740		kingpig9	Tents (JOI18_tents)	C++11	100 / 100	1456 ms	142880 KiB

tents

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 3018;
const int MOD = 1e9 + 7;

//#define debug(...) fprintf(stderr, __VA_ARGS__)
#define debug(...)
#define fi first
#define se second
#define all(v) (v).begin(), (v).end()
#define fillchar(a, s) memset((a), (s), sizeof(a))

void addeq (int &x, int y) {
	x += y;
	if (x >= MOD) {
		x -= MOD;
	}
}

int add (int x, int y) {
	addeq(x, y);
	return x;
}

int mult (int x, int y) {
	return ll(x) * y % MOD;
}

int mult (int x, int y, int z) {
	return mult(mult(x, y), z);
}

int mult (int x, int y, int z, int w) {
	return mult(mult(x, y), mult(z, w));
}

int cho2[MAXN];

void precomp() {
	for (int i = 2; i < MAXN; i++) {
		cho2[i] = i * (i - 1) / 2;
	}
}

int N, M;
int dp[MAXN][MAXN];
int psum1[MAXN][MAXN], psum2[MAXN][MAXN], psum3[MAXN][MAXN];

void compute_psum (int j) {
	int p = 0;
	for (int i = 0; i <= N; i++) {
		addeq(p, mult(4, j + 1, dp[i][j]));
		psum1[i][j] = p;
	}

	p = 0;
	for (int i = 0; i <= N; i++) {
		addeq(p, mult(cho2[j + 2], dp[i][j]));
		psum2[i][j] = p;
	}

	p = 0;
	for (int i = 0; i <= N; i++) {
		addeq(p, mult(j + 1, i + 1, dp[i][j]));
		psum3[i][j] = p;
	}
}

int main() {
	precomp();
	scanf("%d %d", &N, &M);

	for (int i = 0; i < MAXN; i++) {
		for (int j = 0; j < MAXN; j++) {
			dp[i][j] = 1;
		}
	}

	compute_psum(0);
	for (int j = 1; j <= M; j++) {
		for (int i = 1; i <= N; i++) {
			addeq(dp[i][j], psum1[i - 1][j - 1]);
			if (j > 1) {
				addeq(dp[i][j], psum2[i - 1][j - 2]);
			}
			if (i > 1) {
				addeq(dp[i][j], psum3[i - 2][j - 1]);
			}
		}
		compute_psum(j);
	}
	printf("%d\n", add(dp[N][M], MOD - 1));
}

컴파일 시 표준 에러 (stderr) 메시지

tents.cpp: In function 'int main()':
tents.cpp:76:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &N, &M);
  ~~~~~^~~~~~~~~~~~~~~~~

• Subtask 1: 48 / 48
• Subtask 2: 52 / 52