oj.uz

Submission #57527

# Submission time Handle Problem Language Result Execution time Memory
57527 2018-07-15T08:13:40 Z kajebiii Skyscraper (JOI16_skyscraper) C++17
15 / 100
 5 ms 1080 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1000 KB Output is correct
2 Correct 2 ms 1000 KB Output is correct
3 Correct 4 ms 1000 KB Output is correct
4 Correct 3 ms 1012 KB Output is correct
5 Correct 4 ms 1016 KB Output is correct
6 Correct 5 ms 1020 KB Output is correct
7 Correct 3 ms 1020 KB Output is correct
8 Correct 5 ms 1028 KB Output is correct
9 Correct 5 ms 1080 KB Output is correct
10 Correct 3 ms 1080 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -