Submission #133460

#	TimeUTC-0	Username	Problem	Language	Result	Execution time	Memory
133460	2019-07-20 19:14:13	win11905	Skyscraper (JOI16_skyscraper)	C++11	100 / 100	318 ms	260708 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 long M = 1e9+7;
const int N = 105;
const int L = 1005;
int n, m;
int arr[N];
long dp[N][N][L][3];
long mic(int i, int j, int k, int l) {
    if(i != 0 && (j <= 0 || l > 2)) return 0;
    long &z = dp[i][j][k][l];
    if(z != -1) return z;
    if(i == n) return (j == 1 && l == 2);
    int v = (arr[i+1] - arr[i]) * (2*j - l) + k;
    if(v > m) return 0;
    z = (2 * j - l) * mic(i+1, j, v, l) % M;
    z = (z + (j + 1 - l) * mic(i+1, j+1, v, l)) % M;
    z = (z + (2 - l) * mic(i+1, j+1, v, l+1)) % M;
    z = (z + (2 - l) * mic(i+1, j, v, l+1)) % M;
    z = (z + (j - 1) * mic(i+1, j-1, v, l)) % M;
    return z;
}
int main() {
    memset(dp, -1, sizeof dp);
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

Compilation message (stderr)

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

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