Submission #1224336

#	Time	Username	Problem	Language	Result	Execution time	Memory
1224336		nvc2k8	Skyscraper (JOI16_skyscraper)	C++20	100 / 100	53 ms	15628 KiB

skyscraper

#include <bits/stdc++.h>
#define TASK "kasjdkasjd"
#define endl '\n'
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define BIT(i,x) (((i)>>(x))&1)
#define FOR(i,a,b) for(int i = (a); i<=(b); i++)
#define FORD(i,a,b) for(int i = (a); i>=(b); i--)
#define all(C) C.begin(), C.end()
using namespace std;
using ll = long long;
using pii = pair<int,int>;
const int INT_LIM = 2147483647;
const ll LL_LIM = 9223372036854775807;
template <typename X> bool minimize(X &x, const X &y) {if (x>y){x = y; return true;}return false;}
template <typename X> bool maximize(X &x, const X &y) {if (x<y){x = y; return true;}return false;}
///------------------------------------------///
const int MOD = 1e9+7;
void add(int &x, const int &y)
{
    x+=y;
    if (x>=MOD) x-=MOD;
}

int n,l;
int a[105];

int dp[101][101][1005][3];

void inp()
{
    cin >> n >> l;
    FOR(i, 1, n) cin >> a[i];
    sort(a+1, a+1+n);
    a[n+1] = l+1;
}

void solve()
{
    if (n==1)
    {
        cout << 1 << endl; return;
    }
    dp[0][0][0][0] = 1;
    FOR(i, 0, n-1) FOR(c, 0, n-1) FOR(k, 0, l) FOR(close, 0, 2) if (dp[i][c][k][close])
    {
//        cout << i << ' ' << c << ' ' << k << ' ' << close << endl;
        int delta = (a[i+2]-a[i+1]);

        if (close<2)
        {
            int newk = ((c+1)*2-(close+1))*delta+k;
            if (newk<=l) add(dp[i+1][c+1][newk][close+1], 1LL*(2-close)*dp[i][c][k][close]%MOD);

//            if (c>=1)
//            {
                newk = (c*2-(close+1))*delta+k;
                if (newk<=l) add(dp[i+1][c][newk][close+1], 1LL*(2-close)*dp[i][c][k][close]%MOD);
//            }
        }
        if (c>1)
        {
            int newk = ((c-1)*2-close)*delta+k;
            if (newk<=l) add(dp[i+1][c-1][newk][close], 1LL*(c-1)*dp[i][c][k][close]%MOD);
        }
        if (c>=1)
        {
            int newk = (c*2-close)*delta+k;
            if (newk<=l) add(dp[i+1][c][newk][close], 1LL*(c*2-close)*dp[i][c][k][close]%MOD);
        }
        int newk = ((c+1)*2-close)*delta+k;
        if (newk<=l) add(dp[i+1][c+1][newk][close], 1LL*(c+1-close)*dp[i][c][k][close]%MOD);
    }
    int ans = 0;
    FOR(i, 0, l) add(ans, dp[n][1][i][2]);
    cout << ans;
}

signed main()
{
    ///--------------------------///
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    if (fopen(TASK".INP","r")!=NULL)
    {
        freopen(TASK".INP","r",stdin);
        freopen(TASK".OUT","w",stdout);
    }
    ///--------------------------///

    int NTEST = 1;
    bool codeforces = 0;
    if (codeforces) cin >> NTEST;

    while (NTEST--)
    {
        inp();
        solve();
    }

    return 0;
}

///------------------------------------------///

Compilation message (stderr)

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:87:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   87 |         freopen(TASK".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:88:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   88 |         freopen(TASK".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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