Submission #1110010

#	Time	Username	Problem	Language	Result	Execution time	Memory
1110010		InvMOD	Skyscraper (JOI16_skyscraper)	C++14	100 / 100	132 ms	81736 KiB

skyscraper

#include <bits/stdc++.h>
using namespace std;

#define fi first
#define se second
#define gcd __gcd
#define sz(v) (int) v.size()
#define pb push_back
#define pi pair<int,int>
#define all(v) (v).begin(), (v).end()
#define compact(v) (v).erase(unique(all(v)), (v).end())
#define FOR(i, a, b) for(int i = (a); i <= (b); i++)
#define dbg(x) "[" #x " = " << (x) << "]"
#define int long long

using ll = long long;
using ld = long double;
using ull = unsigned long long;

template<typename T> bool ckmx(T& a, const T& b){if(a < b) return a = b, true; return false;}
template<typename T> bool ckmn(T& a, const T& b){if(a > b) return a = b, true; return false;}

const int N = 1e2+5;
const int L = 1e3+5;
const int mod = 1e9+7;


int n, MxL, a[N];

namespace Subtask1{

    int answer, vis[10];
    vector<int> vec;

    void backtrack(int pos = 0){
        if(pos == n){
            int sum = 0;
            for(int i = 1; i < n; i++){
                sum += abs(vec[i] - vec[i-1]);
            }
            answer += (sum <= MxL);
            return;
        }
        for(int i = 1; i <= n; ++i){
            if(vis[i]) continue;

            vis[i] = true;
            vec.pb(a[i]);
            backtrack(pos+1);
            vec.pop_back();
            vis[i] = false;
        }
        return;
    }

    void process()
    {
        answer = 0;
        backtrack();
        cout << answer <<"\n";
    }
}

namespace Subtask3{

    int dp[N][N][L][3];

    void process()
    {
        // thanks a Zero_OP <3 (orz orz)
        if(n == 1){
            cout << "1\n";
            return;
        }

        // Base case: [0]: just put insert a[1] into an cc, [1]: create new cc that contain endpoint (can locate at first or last)
        dp[1][1][0][0] = 1;
        dp[1][1][0][1] = 2;

        for(int i = 1; i < n; i++){
            for(int j = 1; j <= i; j++){
                for(int cost = 0; cost <= MxL; cost++){
                    for(int m = 0; m <= 2; m++){

                        // fill all other cc endpoint with a[i+1]
                        int nxt_cost = cost + (2*j - m) * (a[i+1] - a[i]);

                        if(nxt_cost > MxL) continue;


                        // Insert a[i] to any exist cc (to their endpoint except permutation endpoint)
                        (dp[i+1][j][nxt_cost][m] += dp[i][j][cost][m] * (2*j - m)) %= mod;

                        // Insert a[i] to create permutation endpoint
                        if(m < 2) (dp[i+1][j][nxt_cost][m+1] += dp[i][j][cost][m] * (2 - m)) %= mod;

                        // Insert a[i] to create new cc that does not has endpoint
                        (dp[i+1][j+1][nxt_cost][m] += dp[i][j][cost][m] * (j+1 - m)) %= mod;

                        // Insert a[i] to create new cc with endpoint
                        if(m < 2) (dp[i+1][j+1][nxt_cost][m+1] += dp[i][j][cost][m] * (2 - m)) %= mod;

                        // Merge 2 cc
                        if(j > 1) (dp[i+1][j-1][nxt_cost][m] += dp[i][j][cost][m] * (j-1)) %= mod;
                    }
                }
            }
        }

        int answer = 0;
        for(int i = 0; i <= MxL; i++){
            (answer += dp[n][1][i][2]) %= mod;
        }

        cout << answer <<"\n";
        return;
    }
}

void solve()
{
    cin >> n >> MxL;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    sort(a+1, a+1+n);

    Subtask3::process();
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP","r",stdin);
        freopen(name".OUT","w",stdout);
    }

    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}

Compilation message (stderr)

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

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