Submission #91275

#	Time	Username	Problem	Language	Result	Execution time	Memory
91275		RezwanArefin01	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	208 ms	120604 KiB

skyscraper

///usr/bin/g++ -O2 $0 -o ${0%.cpp} && echo "----------" && ./${0%.cpp}; exit;
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii; 

const int mod = 1e9 + 7; 
int a[101], n, L; 
int dp[101][101][3][1001]; 

void add(int &a, int b) { if((a += b) >= mod) a -= mod; }
#define mul(a, b) ((ll)(a) * (b) % mod)

int f(int i, int c, int e, int cost) {
    cost += (a[i] - a[i - 1]) * (2 * c + e); 
    if(c < 0 || e > 2 || cost > L) return 0;
    if(i == n) return c == 0 && e;

    int &ret = dp[i][c][e][cost]; 
    if(~ret) return ret; 
    ret = 0;
    
    add(ret, mul(c + 1, f(i + 1, c + 1, e, cost))); 
    add(ret, mul(c + e - 1, f(i + 1, c - 1, e, cost))); 
    add(ret, mul(2 * c + e, f(i + 1, c, e, cost))); 
    add(ret, mul(2 - e, f(i + 1, c, e + 1, cost))); 
    add(ret, mul(2 - e, f(i + 1, c - 1, e + 1, cost))); 

    return ret; 
}

int main() {
    scanf("%d %d", &n, &L); 
    for(int i = 1; i <= n; i++) 
        scanf("%d", &a[i]); 
    sort(a + 1, a + n + 1); 
    memset(dp, -1, sizeof dp); 
    printf("%d\n", n == 1 ? 1 : f(1, 0, 0, 0)); 
}

Compilation message (stderr)

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

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