oj.uz

Submission #1110005

# Submission time Handle Problem Language Result Execution time Memory
1110005 2024-11-08T12:22:45 Z InvMOD Skyscraper (JOI16_skyscraper) C++14
0 / 100
 2 ms 2896 KB 
#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

        // 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++){

                        int nxt_cost = (2*j - m) * (a[i+1] - a[i]);

                        if(nxt_cost > MxL) continue;

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

                        // Insert a[i] to create 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);

    if(n < 8) Subtask1::process();
    else
        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

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Incorrect 2 ms 2896 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 2640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Incorrect 2 ms 2896 KB Output isn't correct
6 Halted 0 ms 0 KB -