oj.uz

Submission #877941

# Submission time Handle Problem Language Result Execution time Memory
877941 2023-11-23T22:25:34 Z Ice_man Skyscraper (JOI16_skyscraper) C++14
0 / 100
 3 ms 860 KB 
#include <iostream>
#include <chrono>
#include <algorithm>

#define maxn 15
#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;
}

int dp[(1 << maxn)][maxn][maxdiff];
int val[maxn];
///maxdiff!!!

int n , max_sum;

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

int ans = 0;

void subtask1()
{
    sort(val + 1 , val + 1 + n);
    int cur_sum = 0;
    
    do
    {
        
        cur_sum = 0;
        
        for(int 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(int mask = 1; mask < (1 << n) - 1; mask++)
    {
        for(int i = 0; i < n; i++)
        {
            for(int j = 0; j < max_sum; j++)
            {
                if(dp[mask][i][j])
                {
                    
                    for(int k = 1; k <= n; k++)
                    {
                        if(!(mask & (1 << (k - 1))))
                        {
                            
                            int new_mask = (mask | (1 << (k - 1)));
                            
                            int 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(int i = 1; i <= n; i++)
        for(int j = 0; j <= max_sum; j++)
        ans = (ans + dp[(1 << n) - 1][i][j]) % mod;
        
    cout << ans << endl;
    
}

int main()
{

#ifdef ONLINE_JUDGE
    freopen("taxi.in", "r", stdin);
    freopen("taxi.out", "w", stdout);
#endif

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

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

    read();
    
    if(n <= 7) subtask1();
    else subtask2();

    return 0;
}

Compilation message

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

Subtask #1
0 / 5.0

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

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 860 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 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -