oj.uz

답안 #526847

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
526847 2022-02-16T09:28:29 Z Gromp15 Skyscraper (JOI16_skyscraper) C++17
20 / 100
 251 ms 198984 KB 
#include <bits/stdc++.h>
#define sz(x) (int)(x).size()
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uid uniform_int_distribution
#define uint unsigned int
#define ld long double
#define ll long long
#define ar array
#define pii pair<int, int>
#define pll pair<ll, ll>
#define f first
#define s second
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rint(l, r) uid<int>(l, r)(rng)
template<class T> using pq = priority_queue<T>;
template<class T> using pqg = priority_queue<T, vector<T>, greater<T>>;
template<class T> bool ckmin(T& a, const T& b) { return b < a ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.f); cerr << ','; __print(x.s); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
const int mod = 1e9+7;
void fadd(ll &a, ll &b) {
    a += b;
    if (a >= mod) a -= mod;
}
void test_case() { 
    int a, l; cin >> a >> l;
    vector<int> t(a);
    for (int &x : t) cin >> x;
    vector<vector<vector<ll>>> dp(1<<a, vector<vector<ll>>(a+1, vector<ll>(l+1)));
    dp[0][a][0] = 1;
    for (int m = 0; m < 1<<a; m++) {
        for (int i = 0; i <= a; i++) {
            if (i != a && !((m>>i)&1)) continue;
            for (int j = 0; j <= l; j++) {
                if (!dp[m][i][j]) continue;
                for (int k = 0; k < a; k++) {
                    if ((m>>k)&1) continue;
                    int new_weight = j + (i<a?abs(t[i]-t[k]):0);
                    if (new_weight <= l) {
                        fadd(dp[m|(1<<k)][k][new_weight], dp[m][i][j]);
                    }
                }
            }
        }
    }
    ll ans = 0;
    for (int i = 0; i < a; i++) {
        for (int j = 0; j <= l; j++) {
            fadd(ans, dp[(1<<a)-1][i][j]);
        }
    }
    cout << ans << '\n';

}
int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
//    cin >> t;
    while (t--) test_case();
}

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 10 ms 17488 KB Output is correct
6 Correct 9 ms 15668 KB Output is correct
7 Correct 4 ms 3264 KB Output is correct
8 Correct 3 ms 1744 KB Output is correct
9 Correct 10 ms 16720 KB Output is correct
10 Correct 2 ms 2512 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 42 ms 29208 KB Output is correct
2 Correct 146 ms 195064 KB Output is correct
3 Correct 193 ms 98920 KB Output is correct
4 Correct 162 ms 198984 KB Output is correct
5 Correct 142 ms 198984 KB Output is correct
6 Correct 251 ms 187444 KB Output is correct
7 Correct 71 ms 68160 KB Output is correct
8 Correct 200 ms 95008 KB Output is correct
9 Correct 249 ms 149044 KB Output is correct
10 Correct 135 ms 171972 KB Output is correct

Subtask #3
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 592 KB Output is correct
5 Correct 10 ms 17488 KB Output is correct
6 Correct 9 ms 15668 KB Output is correct
7 Correct 4 ms 3264 KB Output is correct
8 Correct 3 ms 1744 KB Output is correct
9 Correct 10 ms 16720 KB Output is correct
10 Correct 2 ms 2512 KB Output is correct
11 Correct 42 ms 29208 KB Output is correct
12 Correct 146 ms 195064 KB Output is correct
13 Correct 193 ms 98920 KB Output is correct
14 Correct 162 ms 198984 KB Output is correct
15 Correct 142 ms 198984 KB Output is correct
16 Correct 251 ms 187444 KB Output is correct
17 Correct 71 ms 68160 KB Output is correct
18 Correct 200 ms 95008 KB Output is correct
19 Correct 249 ms 149044 KB Output is correct
20 Correct 135 ms 171972 KB Output is correct
21 Runtime error 8 ms 7960 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -