Submission #133068

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
133068	2019-07-20 06:20:31	PeppaPig	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	378 ms	260616 KiB

skyscraper

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include <bits/stdc++.h>
#define long long long
using namespace std;
const int N = 105;
const int L = 1e3+5;
const int M = 1e9+7;
int n, l, a[N];
long dp[N][N][L][3];
long solve(int pos, int cc, int diff, int ends) {
    if(pos == n + 1) return (cc == 1 && diff <= l && ends == 2);
    if(cc == 0 || diff > l || ends == 3) return 0;
    long &now = dp[pos][cc][diff][ends];
    if(~now) return now;
    
    int ndiff = diff + (a[pos] - a[pos - 1]) * (2 * cc - ends);
    now = 0;
    now = (now + (cc + 1 - ends) * solve(pos + 1, cc + 1, ndiff, ends) % M) % M;
    now = (now + (2 * cc - ends) * solve(pos + 1, cc, ndiff, ends) % M) % M;
    now = (now + (cc - 1) * solve(pos + 1, cc - 1, ndiff, ends) % M) % M;
    now = (now + (2 - ends) * solve(pos + 1, cc + 1, ndiff, ends + 1) % M) % M;
    now = (now + (2 - ends) * solve(pos + 1, cc, ndiff, ends + 1) % M) % M;
    return now;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:35:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &l);
     ~~~~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:36:38: 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", a + i);
                                 ~~~~~^~~~~~~~~~~~~

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