Submission #528076

#	Time	Username	Problem	Language	Result	Execution time	Memory
528076		tht2005	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	62 ms	16360 KiB

skyscraper

#include <bits/stdc++.h>

using namespace std;

const int md = (int)1e9 + 7;
void add(int& a, int b) {
    a += b;
    if(a >= md) a -= md;
}
int mul(int a, int b) {
    return (long long)a * b % md;
}

const int N = 102;
const int M = 1003;
int n, m, res, a[N], f[N][N][M][3];

int main() {
    scanf("%d %d", &n, &m);
    for(int i = 0; i < n; ++i)
        scanf("%d", a + i);
    sort(a, a + n);
    if(n == 1) {
        putchar('1');
    }
    else {
        f[0][1][0][0] = 1;
        f[0][1][0][1] = 2;
        for(int i = 0; i + 2 < n; ++i)
            for(int j = 1; j <= n; ++j)
                for(int k = 0; k <= m; ++k)
                    for(int l = 0; l < 3; ++l) {
                        int ft = f[i][j][k][l];
                        if(ft == 0) continue;
                        int nk = k + (2 * j - l) * (a[i + 1] - a[i]);
                        if(nk > m) continue;
                        add(f[i + 1][j + 1][nk][l], mul(ft, j + 1 - l));
                        if(l < 2) add(f[i + 1][j + 1][nk][l + 1], mul(ft, 2 - l));
                        if(j != l) {
                            add(f[i + 1][j - 1][nk][l], mul(ft, j - 1));
                            if(l < 2) add(f[i + 1][j][nk][l + 1], mul(ft, 2 - l));
                        }
                        add(f[i + 1][j][nk][l], mul(ft, 2 * j - l));
                    }
        for(int k = 0; k <= m; ++k) {
            int nk = k + a[n - 1] - a[n - 2];
            if(nk <= m) add(res, f[n - 2][1][k][1]);
            nk += a[n - 1] - a[n - 2];
            if(nk <= m) add(res, f[n - 2][2][k][2]);
        }
        printf("%d", res);
    }
    return 0;
}

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:19:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   19 |     scanf("%d %d", &n, &m);
      |     ~~~~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:21:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         scanf("%d", a + i);
      |         ~~~~~^~~~~~~~~~~~~

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