제출 #243441

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
243441		BamiTorabi	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	244 ms	2808 KiB

skyscraper

//Sasayego! Sasayego! Shinzou wo Sasageyo!

#include <iostream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstring>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <numeric>
#include <bitset>
#include <ctime>
#define debug(x)  cerr << #x << " = " << x << endl
#define lid (id << 1)
#define rid (lid ^ 1)
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <ll, ll> pll;
typedef pair <int, int> pii;

const int maxN = 1e2 + 5;
const int maxK = 1e3 + 5;
const ll INF = 1e18;
const ll MOD = 1e9 + 7;

int a[maxN], arumin[2][maxN][maxK][3];

int main(){
	time_t START = clock();
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int n, L; scanf("%d%d", &n, &L);
	if (n == 1)
		return printf("1\n"), 0;
	for (int i = 1; i <= n; i++)
		scanf("%d", a + i);
	sort(a, a + n + 1);
	for (int i = n; i; i--)
		a[i] -= a[i - 1];
	arumin[1][0][0][1] = 2;
	arumin[1][0][0][2] = 1;
	for (int i = 2; i <= n; i++){
		bool b = i & 1;
		for (int j = 0; j <= i; j++)
			for (int k = 0; k <= L; k++)
				for (int l = 0; l < 3; l++){
					int t = 2 * j + l;
					arumin[b][j][k][l] = 0;
					if (t >= 2 && (t - 2) * a[i] <= k && j > 0)
						arumin[b][j][k][l] = (0ll + arumin[b][j][k][l] + 1ll * arumin[!b][j - 1][k - (t - 2) * a[i]][l] * (j + l - 1) % MOD) % MOD;
					if (t >= 1 && (t - 1) * a[i] <= k && j > 0 && l < 2)
						arumin[b][j][k][l] = (0ll + arumin[b][j][k][l] + 1ll * arumin[!b][j - 1][k - (t - 1) * a[i]][l + 1] * (l + 1) % MOD) % MOD;
					if (t >= 0 && (t + 0) * a[i] <= k)
						arumin[b][j][k][l] = (0ll + arumin[b][j][k][l] + 1ll * arumin[!b][j + 0][k - (t + 0) * a[i]][l] * (2 * j + l) % MOD) % MOD;
					if (t >= 0 && (t + 1) * a[i] <= k && l < 2)
						arumin[b][j][k][l] = (0ll + arumin[b][j][k][l] + 1ll * arumin[!b][j + 0][k - (t + 1) * a[i]][l + 1] * (l + 1) % MOD) % MOD;
					if (t >= 0 && (t + 2) * a[i] <= k)
						arumin[b][j][k][l] = (0ll + arumin[b][j][k][l] + 1ll * arumin[!b][j + 1][k - (t + 2) * a[i]][l] * (j + 1) % MOD) % MOD;
				}
	}
	int ans = 0;
	for (int i = 0; i <= L; i++)
		ans = (0ll + ans + arumin[n & 1][0][i][0]) % MOD;
	printf("%d\n", ans);
	time_t FINISH = clock();
	cerr << "Execution time: " << (ld)(FINISH - START) / CLOCKS_PER_SEC * 1000.0 << " milliseconds.\n";
	return 0;
}
 

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

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:37:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  int n, L; scanf("%d%d", &n, &L);
            ~~~~~^~~~~~~~~~~~~~~~
skyscraper.cpp:41:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", a + i);
   ~~~~~^~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 15 / 15
• Subtask 3: 80 / 80