Submission #152953

#	Time	Username	Problem	Language	Result	Execution time	Memory
152953		Mercenary	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	240 ms	48500 KiB

skyscraper

#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/trie_policy.hpp>

#define pb push_back
#define mp make_pair
#define taskname "A"

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef long double ld;
typedef pair<int,int> ii;
typedef tree <int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

const int maxn = 105 + 5;
const int maxl = 1005;

const int mod = 1e9 + 7;

int a[maxn] , n , l;
int dp[maxn][maxn][maxl][3];

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    if(fopen(taskname".INP","r")){
		freopen(taskname".INP", "r",stdin);
		freopen(taskname".OUT", "w",stdout);
    }
    cin >> n >> l;
    for(int i= 1 ; i <= n ; ++i)cin >> a[i];
    sort(a + 1 , a + n + 1);
    for(int i = n ; i >= 1 ; --i)a[i] -= a[i - 1];
    if(n == 1)return cout << 1 , 0;
    dp[1][1][0][0] = 1;
    dp[1][1][0][1] = 2;
    for(int i = 1 ; i < n ; ++i){
        a[i] = a[i + 1];
        for(int j = 1 ; j <= i ; ++j){
            for(int t = 0 ; t <= l ; ++t){
                auto add = [&] (int i , int j , int t , int k , int val){
//                    assert(val >= 0);
                    if(t <= l){
                        dp[i][j][t][k] += val;
//                        cout << i << " " << j << " " << t << " " << k << " " << dp[i][j][t][k] << endl;
                        if(dp[i][j][t][k] >= mod)dp[i][j][t][k] -= mod;
                    }
                };
                add(i + 1 , j + 1 , t + 2 * j * a[i] , 1 , 2 * dp[i][j][t][0] % mod);//add end or start
                add(i + 1 , j , t + 2 * j * a[i] , 1 , (ll)2 * j * dp[i][j][t][0] % mod);//add end or start and connect to 1 component
                if(i + 1 < n)add(i + 1 , j + 1 , t + 2 * j * a[i] , 0 , dp[i][j][t][0]);
                add(i + 1 , j , t + 2 * j * a[i] , 0 , 2ll * j * dp[i][j][t][0] % mod);
                if(j >= 2)add(i + 1 , j - 1 , t + 2 * j * a[i] , 0 , (ll)j * (j - 1) % mod * dp[i][j][t][0] % mod);

                add(i + 1 , j + 1 , t + (2 * j - 1) * a[i] , 2 , dp[i][j][t][1]);
                if(j > 1)add(i + 1 , j , t + (2 * j - 1) * a[i] , 2 , (ll)(j - 1) * dp[i][j][t][1] % mod);
                add(i + 1 , j , t + (2 * j - 1) * a[i] , 1 , dp[i][j][t][1]);
                add(i + 1 , j - 1 , t + (2 * j - 1) * a[i] , 1 , 1ll * (j - 1) * dp[i][j][t][1] % mod);
                if(i + 1 < n)add(i + 1 , j + 1 , t + (2 * j - 1) * a[i] , 1 , dp[i][j][t][1]);
                if(j >= 1)add(i + 1 , j , t + (2 * j - 1) * a[i] , 1 , 2ll * (j - 1) * dp[i][j][t][1] % mod);
                if(j >= 3)add(i + 1 , j - 1 , t + (2 * j - 1) * a[i] , 1 , (ll)(j - 1) * (j - 2) % mod * dp[i][j][t][1] % mod);

                if(i + 1 < n)add(i + 1 , j + 1 , t + (2 * j - 2) * a[i] , 2 , dp[i][j][t][2]);
                add(i + 1 , j , t + (2 * j - 2) * a[i] , 2 , 2 * dp[i][j][t][2] % mod);
                add(i + 1 , j - 1, t + (2 * j - 2) * a[i] , 2 , 2ll * (j - 2) * dp[i][j][t][2] % mod);
                if(j >= 2)add(i + 1 , j , t + (2 * j - 2) * a[i] , 2 , 2ll * (j - 2) * dp[i][j][t][2] % mod);
                if(j >= 4)add(i + 1 , j - 1 , t + (2 * j - 2) * a[i] , 2 , (ll)(j - 2) * (j - 3) % mod * dp[i][j][t][2] % mod);
            }
        }
    }
    for(int i = 2 ; i <= n ; ++i){
        for(int j = 1 ; j <= i ; ++j){
            for(int t = 0 ; t <= l ; ++t){
//                cout << i << " " << j << " " << t << " " << dp[i][j][t][0] << " " << dp[i][j][t][1] << " " << dp[i][j][t][2] << endl;
            }
        }
    }
    int res = 0;
    for(int i = 1 ; i <= l ; ++i){
        if(i - 2 * a[n] >= 0){
            res += dp[n - 1][2][i - 2 * a[n]][2];
            if(res >= mod)res -= mod;
        }
        if(i - a[n] >= 0){
            res += dp[n - 1][1][i - a[n]][1] % mod;
            if(res >= mod)res -= mod;
        }
    }
//    cerr << dp[n][1][l][2];
    cout << res;
}

Compilation message (stderr)

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

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