oj.uz

Submission #91042

# Submission time Handle Problem Language Result Execution time Memory
91042 2018-12-26T00:13:55 Z tincamatei Skyscraper (JOI16_skyscraper) C++14
20 / 100
 164 ms 37168 KB 
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100;
const int MAX_L = 1000;
const int MOD = 1000000007;
int v[1+MAX_N];

int dp[1+MAX_N][1+MAX_N+1][1+MAX_L][3];

int main() {
#ifdef HOME
	FILE *fin = fopen("input.in", "r");
	FILE *fout = fopen("output.out", "w");
#else
	FILE *fin = stdin;
	FILE *fout = stdout;
#endif

	int n, l;

	fscanf(fin, "%d%d", &n, &l);
	
	for(int i = 1; i <= n; ++i)
		fscanf(fin, "%d", &v[i]);
	sort(v + 1, v + 1 + n);

	if(n == 1) {
		fprintf(fout, "%d", 1);
	} else {
		dp[0][0][0][0] = 1;
		for(int N = 1; N <= n; ++N)
			for(int C = 1; C <= N; ++C)
				for(int L = 0; L <= l; ++L)
					for(int E = 0; E <= 2; ++E) {
						int scad;

						// Componenta noua:
						scad = ((C - 1) * 2 - E) * (v[N] - v[N - 1]);
						if(L >= scad)
							dp[N][C][L][E] = (dp[N - 1][C - 1][L - scad][E] * (C - E) + dp[N][C][L][E]) % MOD;
						
						// Atasez la o componenta
						scad = (C * 2 - E) * (v[N] - v[N - 1]);
						if(L >= scad)
							dp[N][C][L][E] = ((long long)dp[N - 1][C][L - scad][E] * (C * 2 - E) + dp[N][C][L][E]) % MOD;
						
						// Unesc doua componente
						scad = ((C + 1) * 2 - E) * (v[N] - v[N - 1]);
						if(L >= scad)
							dp[N][C][L][E] = ((long long)dp[N - 1][C + 1][L - scad][E] * C + dp[N][C][L][E]) % MOD;
						
						// Imi creez o componenta intr-o margine
						scad = ((C - 1) * 2 - (E - 1)) * (v[N] - v[N - 1]);
						if(L >= scad && E >= 1)
							dp[N][C][L][E] = ((long long)dp[N - 1][C - 1][L - scad][E - 1] * (2 - E + 1) + dp[N][C][L][E]) % MOD;
						
						// Atasez la o componenta si fixez marginea
						scad = (2 * C - (E - 1)) * (v[N] - v[N - 1]);
						if(L >= scad && E >= 1)
							dp[N][C][L][E] = ((long long)dp[N - 1][C][L - scad][E - 1] * (2 - E + 1) + dp[N][C][L][E]) % MOD;
					}
		
		int rez = 0;
		for(int i = 0; i <= l; ++i)
			rez = (rez + dp[n][1][i][2]) % MOD;
		fprintf(fout, "%d", rez % MOD);
	}
#ifdef HOME
	fclose(fin);
	fclose(fout);
#endif
	return 0;
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:23:8: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  fscanf(fin, "%d%d", &n, &l);
  ~~~~~~^~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:26:9: warning: ignoring return value of 'int fscanf(FILE*, const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   fscanf(fin, "%d", &v[i]);
   ~~~~~~^~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 532 KB Output is correct
2 Correct 2 ms 616 KB Output is correct
3 Correct 2 ms 792 KB Output is correct
4 Correct 2 ms 828 KB Output is correct
5 Correct 3 ms 1088 KB Output is correct
6 Correct 3 ms 1088 KB Output is correct
7 Correct 2 ms 1088 KB Output is correct
8 Correct 2 ms 1088 KB Output is correct
9 Correct 3 ms 1160 KB Output is correct
10 Correct 2 ms 1160 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1168 KB Output is correct
2 Correct 2 ms 1212 KB Output is correct
3 Correct 2 ms 1308 KB Output is correct
4 Correct 2 ms 1320 KB Output is correct
5 Correct 2 ms 1320 KB Output is correct
6 Correct 2 ms 1360 KB Output is correct
7 Correct 2 ms 1364 KB Output is correct
8 Correct 2 ms 1412 KB Output is correct
9 Correct 3 ms 1432 KB Output is correct
10 Correct 2 ms 1432 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 532 KB Output is correct
2 Correct 2 ms 616 KB Output is correct
3 Correct 2 ms 792 KB Output is correct
4 Correct 2 ms 828 KB Output is correct
5 Correct 3 ms 1088 KB Output is correct
6 Correct 3 ms 1088 KB Output is correct
7 Correct 2 ms 1088 KB Output is correct
8 Correct 2 ms 1088 KB Output is correct
9 Correct 3 ms 1160 KB Output is correct
10 Correct 2 ms 1160 KB Output is correct
11 Correct 10 ms 1168 KB Output is correct
12 Correct 2 ms 1212 KB Output is correct
13 Correct 2 ms 1308 KB Output is correct
14 Correct 2 ms 1320 KB Output is correct
15 Correct 2 ms 1320 KB Output is correct
16 Correct 2 ms 1360 KB Output is correct
17 Correct 2 ms 1364 KB Output is correct
18 Correct 2 ms 1412 KB Output is correct
19 Correct 3 ms 1432 KB Output is correct
20 Correct 2 ms 1432 KB Output is correct
21 Correct 6 ms 3616 KB Output is correct
22 Incorrect 164 ms 37168 KB Output isn't correct
23 Halted 0 ms 0 KB -