oj.uz

Submission #877974

# Submission time Handle Problem Language Result Execution time Memory
877974 2023-11-23T23:20:48 Z Ice_man Skyscraper (JOI16_skyscraper) C++14
100 / 100
 135 ms 347620 KB 
#include <iostream>
#include <chrono>
#include <algorithm>
#include <cstring>
#include <cassert>

#define maxn 105
#define maxdiff 1005
#define maxlog 20
#define INF 1000000010
#define LINF 1000000000000000005
#define mod 1000000007
#define endl '\n'
#define pb(x) push_back(x)
#define X first
#define Y second
#define control cout<<"passed"<<endl;

#pragma GCC optimize("O3" , "Ofast" , "fast-math" , "unroll-loops")
#pragma GCC target(avx2)

using namespace std;

std::chrono::high_resolution_clock::time_point startT, currT;
constexpr double TIME_MULT = 1;

double timePassed()
{
    using namespace std::chrono;
    currT = high_resolution_clock::now();
    double time = duration_cast<duration<double>>(currT - startT).count();
    return time * TIME_MULT;
}

///long long dp[(1 << 15)][15][500];
long long val[maxn];
///maxdiff!!!

long long n , max_sum;

void read()
{
    cin >> n >> max_sum;
    for(long long i = 1; i <= n; i++) cin >> val[i];

    sort(val + 1 , val + 1 + n);
    val[0] = val[1];
}

long long ans = 0;

void subtask1()
{
    sort(val + 1 , val + 1 + n);
    long long cur_sum = 0;
    do
    {
        cur_sum = 0;

        for(long long i = 2; i <= n; i++) cur_sum += abs(val[i - 1] - val[i]);

        if(cur_sum <= max_sum) ans++;

    }while(next_permutation(val + 1 , val + 1 + n));

    cout << ans << endl;

}

/**void subtask2()
{

    dp[0][0][0] = 1;

    for(long long mask = 0; mask < (1 << n) - 1; mask++)
    {
        for(long long i = 0; i <= n; i++)
        {
            for(long long j = 0; j <= max_sum; j++)
            {
                if(dp[mask][i][j])
                {

                    for(long long k = 1; k <= n; k++)
                    {
                        if(!(mask & (1 << (k - 1))))
                        {

                            long long new_mask = (mask | (1 << (k - 1)));

                            long long pom;
                            if(mask == 0) pom = 0;
                            else pom = j + abs(val[i] - val[k]);

                            dp[new_mask][k][pom] = (dp[new_mask][k][pom] + dp[mask][i][j]) % mod;


                        }
                    }

                }
            }
        }
    }


    for(long long i = 1; i <= n; i++)
        for(long long j = 0; j <= max_sum; j++)
        ans = (ans + dp[(1 << n) - 1][i][j]) % mod;

    cout << ans << endl;

}*/

long long dp2[maxn][maxn][maxdiff][2][2];

long long subtask3(long long sum , long long l , long long r , long long i , long long j)
{

    long long new_sum = sum + (j * 2 + l + r) * (val[i] - val[i - 1]);
    if(new_sum > max_sum) return 0;

    if(j < 0) return 0;
    if(i == n) return j == 0;

    long long &cur_ans = dp2[i][j][sum][l][r];
    if(cur_ans != -1) return cur_ans;

    cur_ans = 0;

    cur_ans += subtask3(new_sum , l , 1 , i + 1, j);            ///dqsno
    cur_ans += subtask3(new_sum , l , 1 , i + 1 , j - 1) * j;

    cur_ans += subtask3(new_sum , 1 , r , i + 1 , j);           ///lqvo
    cur_ans += subtask3(new_sum , 1 , r , i + 1 , j - 1) * j;

    cur_ans += subtask3(new_sum , l , r , i + 1 , j) * 2 * j; /// dobavi

    cur_ans += subtask3(new_sum , l , r , i + 1 , j + 1); ///novo

    cur_ans += subtask3(new_sum , l , r , i + 1 , j - 1) * (j - 1) * j; ///mergeni

    cur_ans %= mod;
    return (cur_ans % mod);
}




int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    startT = std::chrono::high_resolution_clock::now();

    ///control

    read();

    ///

    if(n <= 8) subtask1();
    ///else if(n <= 14) subtask2();
    else
    {
        memset(dp2 , -1 , sizeof(dp2));

        ///assert(false);

        cout << subtask3(0 , 0 , 0 , 1 , 0) << endl;
    }

    return 0;
}

Compilation message

skyscraper.cpp:20:20: warning: '#pragma GCC option' is not a string [-Wpragmas]
   20 | #pragma GCC target(avx2)
      |                    ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 500 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 84 ms 347480 KB Output is correct
2 Correct 40 ms 347220 KB Output is correct
3 Correct 39 ms 347216 KB Output is correct
4 Correct 39 ms 347304 KB Output is correct
5 Correct 40 ms 347220 KB Output is correct
6 Correct 40 ms 347220 KB Output is correct
7 Correct 40 ms 347220 KB Output is correct
8 Correct 39 ms 347216 KB Output is correct
9 Correct 39 ms 347216 KB Output is correct
10 Correct 39 ms 347220 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 500 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 84 ms 347480 KB Output is correct
12 Correct 40 ms 347220 KB Output is correct
13 Correct 39 ms 347216 KB Output is correct
14 Correct 39 ms 347304 KB Output is correct
15 Correct 40 ms 347220 KB Output is correct
16 Correct 40 ms 347220 KB Output is correct
17 Correct 40 ms 347220 KB Output is correct
18 Correct 39 ms 347216 KB Output is correct
19 Correct 39 ms 347216 KB Output is correct
20 Correct 39 ms 347220 KB Output is correct
21 Correct 41 ms 347228 KB Output is correct
22 Correct 135 ms 347220 KB Output is correct
23 Correct 128 ms 347216 KB Output is correct
24 Correct 121 ms 347368 KB Output is correct
25 Correct 125 ms 347220 KB Output is correct
26 Correct 124 ms 347416 KB Output is correct
27 Correct 63 ms 347220 KB Output is correct
28 Correct 74 ms 347220 KB Output is correct
29 Correct 109 ms 347296 KB Output is correct
30 Correct 129 ms 347620 KB Output is correct