oj.uz

Submission #877969

# Submission time Handle Problem Language Result Execution time Memory
877969 2023-11-23T23:06:18 Z Ice_man Skyscraper (JOI16_skyscraper) C++14
5 / 100
 23 ms 174752 KB 
#include <iostream>
#include <chrono>
#include <algorithm>
#include <cstring>
#include <cassert>

#define maxn 105
#define maxdiff 505
#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);

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

    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 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 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 600 KB Output is correct

Subtask #2
0 / 15.0

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

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 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 600 KB Output is correct
11 Incorrect 23 ms 174752 KB Output isn't correct
12 Halted 0 ms 0 KB -