oj.uz

Submission #638005

# Submission time Handle Problem Language Result Execution time Memory
638005 2022-09-04T07:46:52 Z Do_you_copy Skyscraper (JOI16_skyscraper) C++17
100 / 100
 70 ms 51092 KB 
#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pb push_back
#define faster ios_base::sync_with_stdio(0); cin.tie(0);
using namespace std;
using ll = long long;
using ull = unsigned ll;
using ld = long double;
using pii = pair <int, int>;
using pil = pair <int, ll>;
using pli = pair <ll, int>;
using pll = pair <ll, ll>;
mt19937 Rand(chrono::steady_clock::now().time_since_epoch().count());

ll min(const ll &a, const ll &b){
    return (a < b) ? a : b;
}

ll max(const ll &a, const ll &b){
    return (a > b) ? a : b;
}

const ll Mod = 1000000007;
//const ll Mod2 = 999999999989;
//only use when required
const int maxN = 1e2 + 10;
const int maxL = 1e3 + 10;
int n, L;
int a[maxN];
ll dp[maxN][maxN][maxL][3];

void Init(){
    cin >> n >> L;
    a[n] = 1e7;
    if (n == 1){
        cout << 1; return;
    }
    for (int i = 0; i < n; ++i) cin >> a[i];
    sort(a, a + n);
    dp[0][0][0][0] = 1;
    for (int i = 1; i <= n; ++i){
        for (int j = 1; j <= i; ++j){
            for (int k = 0; k <= L; ++k){
                for (int m = 0; m <= 2; ++m){
                    ll delta = (2 * j - m) * (a[i] - a[i - 1]);
                    if (delta > k|| i + j + 1 - m > n) continue;
                    dp[i][j][k][m] += dp[i - 1][j - 1][k - delta][m];
                    if (m > 0){
                        dp[i][j][k][m] += (3 - m) * dp[i - 1][j - 1][k - delta][m - 1];
                        if (m == 1) dp[i][j][k][m] += 2 * j * dp[i - 1][j][k - delta][m - 1];
                        else if (m == 2 && i == n) dp[i][j][k][m] += dp[i - 1][j][k - delta][m - 1];
                        else dp[i][j][k][m] += (j - 1) * dp[i - 1][j][k - delta][m - 1];
                    }
                    dp[i][j][k][m] += (2 * j - m) * dp[i - 1][j][k - delta][m];
                    if (m == 2 && i == n) dp[i][j][k][m] += dp[i - 1][j + 1][k - delta][m];
                    else if (m == 2) dp[i][j][k][m] += j * (j - 1) * dp[i - 1][j + 1][k - delta][m];
                    else if (m == 1) dp[i][j][k][m] += j * j * dp[i - 1][j + 1][k - delta][m];
                    else dp[i][j][k][m] += j * (j + 1) * dp[i - 1][j + 1][k - delta][m];
                    dp[i][j][k][m] %= Mod;
                }
            }
        }
    }
    ll ans = 0;
    for (int i = 0; i <= L; ++i){
        ans += dp[n][1][i][2];
        ans %= Mod;
    }
    cout << ans;
}

#define debug
#define taskname "test"
signed main(){
    if (fopen(taskname".inp", "r")){
        freopen(taskname".inp", "r", stdin);
        #ifdef debug
        freopen(taskname".out", "w", stdout);
        #endif
    }
    faster;
    ll tt = 1;
    //cin >> tt;
    while (tt--){
        Init();
    }
    if (fopen("timeout.txt", "r")){
        ofstream timeout("timeout.txt");
        timeout << 1000 * double(clock()) / CLOCKS_PER_SEC;
        #ifndef debug
        cerr << "\nTime elapsed: " << 1000 * double(clock()) / CLOCKS_PER_SEC << "ms\n";
        #endif
    }
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 1 ms 596 KB Output is correct
3 Correct 1 ms 596 KB Output is correct
4 Correct 1 ms 596 KB Output is correct
5 Correct 1 ms 596 KB Output is correct
6 Correct 1 ms 596 KB Output is correct
7 Correct 1 ms 612 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 596 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 724 KB Output is correct
6 Correct 1 ms 724 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 724 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 596 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 596 KB Output is correct
14 Correct 1 ms 596 KB Output is correct
15 Correct 1 ms 596 KB Output is correct
16 Correct 1 ms 596 KB Output is correct
17 Correct 1 ms 612 KB Output is correct
18 Correct 1 ms 596 KB Output is correct
19 Correct 1 ms 724 KB Output is correct
20 Correct 1 ms 596 KB Output is correct
21 Correct 2 ms 2376 KB Output is correct
22 Correct 45 ms 35784 KB Output is correct
23 Correct 68 ms 47728 KB Output is correct
24 Correct 61 ms 46844 KB Output is correct
25 Correct 70 ms 50844 KB Output is correct
26 Correct 63 ms 46020 KB Output is correct
27 Correct 25 ms 23548 KB Output is correct
28 Correct 30 ms 26896 KB Output is correct
29 Correct 49 ms 41268 KB Output is correct
30 Correct 70 ms 51092 KB Output is correct