oj.uz

Submission #584382

# Submission time Handle Problem Language Result Execution time Memory
584382 2022-06-27T09:56:13 Z thezomb1e Skyscraper (JOI16_skyscraper) C++17
20 / 100
 449 ms 261656 KB 
//thatsramen

#include <bits/stdc++.h>
#pragma GCC target ("avx2")
#pragma GCC optimization ("O3")
#pragma GCC optimization ("unroll-loops")
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

#define eb emplace_back
#define pb push_back
#define ft first
#define sd second
#define pi pair<int, int>
#define pll pair<ll, ll>
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define dbg(...) dbg_out(__VA_ARGS__)

using ll = long long;
using ld = long double;
using namespace std;
using namespace __gnu_pbds;

//Constants
const ll INF = 5 * 1e18;
const int IINF = 2 * 1e9;
const ll MOD = 1e9 + 7;
// const ll MOD = 998244353;
const ll dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
const ld PI = 3.14159265359;

//Templates
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) {return os << '(' << p.first << ", " << p.second << ')';}
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) {os << '['; string sep; for (const T &x : v) os << sep << x, sep = ", "; return os << ']';}
void dbg_out() {cerr << endl;}
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << H << ' '; dbg_out(T...); }
template<typename T> void mins(T& x, T y) {x = min(x, y);}
template<typename T> void maxs(T& x, T y) {x = max(x, y);}
template<typename T> using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T> using omset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;

//order_of_key(k): number of elements strictly less than k
//find_by_order(k): k-th element in the set

void setPrec() {cout << fixed << setprecision(15);}
void unsyncIO() {cin.tie(0)->sync_with_stdio(0);}
void setIn(string s) {freopen(s.c_str(), "r", stdin);}
void setOut(string s) {freopen(s.c_str(), "w", stdout);}
void setIO(string s = "") {
    unsyncIO(); setPrec();
    if(s.size()) setIn(s + ".in"), setOut(s + ".out");
}

// #define TEST_CASES

void solve() {
    int n, l;
    cin >> n >> l;
    vector<int> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    vector<vector<vector<ll>>> dp((1 << n) + 5, vector<vector<ll>> (n + 5, vector<ll> (l + 5, 0)));
    for (int i = 0; i < n; i++) {
        int mask = 1 << i;
        dp[mask][i][0]++;
    }
    for (int mask = 1; mask < (1 << n); mask++) {
        for (int i = 0; i < n; i++) {
            if (!(mask & (1 << i))) {
                int nw = mask | (1 << i);
                for (int last = 0; last < n; last++) {
                    if (mask & (1 << last)) {
                        for (int j = 0; j <= l; j++) {
                            if (j + abs(a[i] - a[last]) <= l)
                                (dp[nw][i][j + abs(a[i] - a[last])] += dp[mask][last][j]) %= MOD;
                        }
                    }
                }
            }
        } 
    }
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j <= l; j++) {
            (ans += dp[(1 << n) - 1][i][j]) %= MOD;
        }
    }
    cout << ans;
}

int main() {
    setIO();

    int tt = 1;
    #ifdef TEST_CASES
        cin >> tt;
    #endif

    while (tt--)
        solve();

    return 0;
}

Compilation message

skyscraper.cpp:5: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    5 | #pragma GCC optimization ("O3")
      | 
skyscraper.cpp:6: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    6 | #pragma GCC optimization ("unroll-loops")
      | 
skyscraper.cpp: In function 'void setIn(std::string)':
skyscraper.cpp:48:30: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   48 | void setIn(string s) {freopen(s.c_str(), "r", stdin);}
      |                       ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp: In function 'void setOut(std::string)':
skyscraper.cpp:49:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   49 | void setOut(string s) {freopen(s.c_str(), "w", stdout);}
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 24 ms 25712 KB Output is correct
6 Correct 19 ms 23108 KB Output is correct
7 Correct 5 ms 4820 KB Output is correct
8 Correct 3 ms 2516 KB Output is correct
9 Correct 21 ms 24660 KB Output is correct
10 Correct 4 ms 3796 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 40268 KB Output is correct
2 Correct 410 ms 256788 KB Output is correct
3 Correct 268 ms 134900 KB Output is correct
4 Correct 405 ms 261656 KB Output is correct
5 Correct 419 ms 261652 KB Output is correct
6 Correct 449 ms 247120 KB Output is correct
7 Correct 174 ms 95896 KB Output is correct
8 Correct 252 ms 130020 KB Output is correct
9 Correct 398 ms 198284 KB Output is correct
10 Correct 359 ms 227556 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 852 KB Output is correct
5 Correct 24 ms 25712 KB Output is correct
6 Correct 19 ms 23108 KB Output is correct
7 Correct 5 ms 4820 KB Output is correct
8 Correct 3 ms 2516 KB Output is correct
9 Correct 21 ms 24660 KB Output is correct
10 Correct 4 ms 3796 KB Output is correct
11 Correct 62 ms 40268 KB Output is correct
12 Correct 410 ms 256788 KB Output is correct
13 Correct 268 ms 134900 KB Output is correct
14 Correct 405 ms 261656 KB Output is correct
15 Correct 419 ms 261652 KB Output is correct
16 Correct 449 ms 247120 KB Output is correct
17 Correct 174 ms 95896 KB Output is correct
18 Correct 252 ms 130020 KB Output is correct
19 Correct 398 ms 198284 KB Output is correct
20 Correct 359 ms 227556 KB Output is correct
21 Runtime error 7 ms 9588 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -