Submission #57527

#	Time	Username	Problem	Language	Result	Execution time	Memory
57527		kajebiii	Skyscraper (JOI16_skyscraper)	C++17	15 / 100	5 ms	1080 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

#define SZ(v) ((int)(v).size())
#define ALL(v) (v).begin(),(v).end()
#define one first
#define two second
typedef long long ll;
typedef pair<int, int> pi;
const int INF = 0x3f2f1f0f;
const ll LINF = 1ll * INF * INF;

const int MAX_N = 1e2 + 10, MAX_L = 1e3 + 10, MOD = 1e9 + 7;

int N, L, Nr[MAX_N];
ll Dy[MAX_N][MAX_N][MAX_L][4];
void add(ll &a, ll b) {
	a = (a+b)%MOD;
}
int main() {
	cin >> N >> L;
	for(int i=1; i<=N; i++) scanf("%d", &Nr[i]);
	sort(Nr+1, Nr+N+1);
	
	int cnts[4] = {0, 1, 1, 2};
	Dy[0][0][0][0] = 1;
	for(int i=1; i<=N; i++) for(int j=1; j<=i; j++) {
		ll diff = Nr[i] - Nr[i-1];
		for(int s=1; s<4; s++) {
			int cnt = cnts[s] - 1;
			for(int x=1; x<=2; x++) {
				if(s&x) {
					int base0 = (2*j-cnt)*diff;
					for(int k=base0; k<=L; k++)
						add(Dy[i][j][k][s], Dy[i-1][j][k-base0][s&(3-x)]);
					int base1 = (2*(j-1)-cnt)*diff;
					for(int k=base1; k<=L; k++)
						add(Dy[i][j][k][s], Dy[i-1][j-1][k-base1][s&(3-x)]);
				}
			}
		}
		for(int s=0; s<4; s++) {
			int cnt = cnts[s];
			int base0 = (2*(j+1)-cnt)*diff;
			for(int k=base0; k<=L; k++)
				add(Dy[i][j][k][s], Dy[i-1][j+1][k-base0][s] * j);
			int base1 = (2*(j-1)-cnt)*diff;
			for(int k=base1; k<=L; k++)
				add(Dy[i][j][k][s], Dy[i-1][j-1][k-base1][s] * (j-cnt));
			int base2 = (2*j-cnt)*diff;
			for(int k=base2; k<=L; k++)
				add(Dy[i][j][k][s], Dy[i-1][j][k-base2][s] * (2*j-cnt));
		}
		//for(int k=0; k<=L; k++) for(int s=0; s<4; s++) if(Dy[i][j][k][s]) printf("%d %d %d %d : %lld\n", i, j, k, s, Dy[i][j][k][s]);
	}
	ll ans = 0;
	for(int k=0; k<=L; k++) ans += Dy[N][1][k][3], ans %= MOD;
	printf("%lld\n", ans);
	return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:23:31: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1; i<=N; i++) scanf("%d", &Nr[i]);
                          ~~~~~^~~~~~~~~~~~~~

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