oj.uz

Submission #876813

# Submission time Handle Problem Language Result Execution time Memory
876813 2023-11-22T11:27:30 Z vjudge1 Skyscraper (JOI16_skyscraper) C++17
5 / 100
 940 ms 210772 KB 
#include <bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define uniq(x) x.erase(unique(all(x)), x.end())
#define rall(x) x.rbegin(), x.rend()
//#define int long long

using namespace std;

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 5;
const double eps = 1e-9;

void setIO() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

int n, L;
vector<int> v;
vector<vector<vector<ll> > > dp;

ll f(int mask, int last, int total) {
    if(total > L) return 0;
    if(__builtin_popcount(mask) == n) return 1;
    if(dp[mask][last][total] != -1) return dp[mask][last][total];

    ll ans = 0;
    for(int i=0; i<n; i++) {
        if(mask & (1 << i)) continue;
        int newTotal = total + (last == n ? 0 : abs(v[i] - v[last]));
        ans += f(mask | (1 << i), i, newTotal);
    }

    return dp[mask][last][total] = ans;
}

int32_t main() {
    setIO();

    cin >> n >> L;
    v.resize(n);
    for(int &x : v) cin >> x;

    if(n <= 8)
        dp.resize(1<<n, vector<vector<ll> >(n+1, vector<ll>(1005, -1)));
    else if(n > 8 && n <= 14)
        dp.resize(1<<n, vector<vector<ll> >(n+1, vector<ll>(105, -1)));

    cout << f(0, n, 0) << '\n';
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 2 ms 3932 KB Output is correct
5 Correct 8 ms 18524 KB Output is correct
6 Correct 8 ms 18524 KB Output is correct
7 Correct 8 ms 18528 KB Output is correct
8 Correct 8 ms 18520 KB Output is correct
9 Correct 8 ms 18524 KB Output is correct
10 Correct 9 ms 18704 KB Output is correct

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 114 ms 45920 KB Output is correct
2 Correct 159 ms 210520 KB Output is correct
3 Correct 656 ms 210772 KB Output is correct
4 Correct 145 ms 210668 KB Output is correct
5 Correct 134 ms 210668 KB Output is correct
6 Correct 637 ms 210660 KB Output is correct
7 Correct 135 ms 210476 KB Output is correct
8 Correct 614 ms 210660 KB Output is correct
9 Incorrect 940 ms 210656 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 2 ms 3932 KB Output is correct
5 Correct 8 ms 18524 KB Output is correct
6 Correct 8 ms 18524 KB Output is correct
7 Correct 8 ms 18528 KB Output is correct
8 Correct 8 ms 18520 KB Output is correct
9 Correct 8 ms 18524 KB Output is correct
10 Correct 9 ms 18704 KB Output is correct
11 Correct 114 ms 45920 KB Output is correct
12 Correct 159 ms 210520 KB Output is correct
13 Correct 656 ms 210772 KB Output is correct
14 Correct 145 ms 210668 KB Output is correct
15 Correct 134 ms 210668 KB Output is correct
16 Correct 637 ms 210660 KB Output is correct
17 Correct 135 ms 210476 KB Output is correct
18 Correct 614 ms 210660 KB Output is correct
19 Incorrect 940 ms 210656 KB Output isn't correct
20 Halted 0 ms 0 KB -