oj.uz

Submission #528004

# Submission time Handle Problem Language Result Execution time Memory
528004 2022-02-19T01:49:08 Z tphuc2908 Skyscraper (JOI16_skyscraper) C++14
20 / 100
 391 ms 476756 KB 
#include<bits/stdc++.h>

using namespace std;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
//#pragma GCC optimization ("unroll-loops")
#define rep(i, x, y) for(int i = x; i <= y; ++i)
#define repi(i,x,y) for(int i = x; i >= y; --i)
#define ci(x) int x; cin>> x
#define TC(t) ci(t); while(t--)
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define cii(x, y) ci(x); ci(y)
#define ciii(x, y, z) ci(x); ci(y); ci(z)
#define mp make_pair
//#define int long long
typedef long long ll;
typedef vector<int> vi;
const int N = 8e2 + 5;
const int NN = 16 + 15;
const int mod = 1e9+7;
const int mod1 = 1e9 + 9;
const int pi = 31;
const ll inf = 1e15 + 6;
const int block = 500;
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, -1, 0, 1};

void readfile(){
    #ifdef ONLINE_JUDGE
    #else
        freopen("text.inp", "r", stdin);
    #endif // ONLINE_JUDGE
//    freopen("text.inp", "r", stdin);
//    freopen("template.out", "w", stdout);
}

int n, L;
int a[N];

void inp(){
    cin >> n >> L;
    for(int i = 1; i <= n; ++i) cin >> a[i];
}

int add(int x, int y){
    x += y;
    while(x < 0) x += mod;
    while(x >= mod) x -= mod;
    return x;
}

int mul(int x, int y){
    return (x * 1LL * y) % mod;
}

int f[(1<<14)][14][1005];

void sub2(){
    for(int i = 0; i < n; ++i)
        f[(1<<i)][i][0] = 1;
    for(int i = 0; i < (1<<n); ++i){
        for(int j = 0; j < n; ++j){
            if(!((i>>j)&1)) continue;
            for(int k = 0; k < n; ++k){
                if(!((i>>k)&1)) continue;
                if(k==j) continue;
                for(int w = 0; w <= L; ++w)
                    if(w + abs(a[j+1] - a[k+1]) <= L)
                        f[i][j][w + abs(a[j+1] - a[k+1])] = add(f[i][j][w + abs(a[j+1] - a[k+1])], f[i^(1<<j)][k][w]);
            }
        }
    }
    int res = 0;
    for(int w = 0; w <= L; ++w)
        for(int i = 0; i < n; ++i)
            res = add(res, f[(1<<n)-1][i][w]);
    cout << res;
}

void process(){
    if(n <= 14) sub2();
}

int main() {
    //readfile();
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    inp();
    process();
    return 0;
}

Compilation message

skyscraper.cpp: In function 'void readfile()':
skyscraper.cpp:34:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |         freopen("text.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 1100 KB Output is correct
5 Correct 7 ms 6048 KB Output is correct
6 Correct 8 ms 5824 KB Output is correct
7 Correct 4 ms 4676 KB Output is correct
8 Correct 4 ms 4484 KB Output is correct
9 Correct 8 ms 5964 KB Output is correct
10 Correct 4 ms 4556 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 101448 KB Output is correct
2 Correct 375 ms 476196 KB Output is correct
3 Correct 322 ms 466316 KB Output is correct
4 Correct 387 ms 476264 KB Output is correct
5 Correct 391 ms 476756 KB Output is correct
6 Correct 373 ms 476128 KB Output is correct
7 Correct 299 ms 462660 KB Output is correct
8 Correct 331 ms 465876 KB Output is correct
9 Correct 350 ms 472260 KB Output is correct
10 Correct 357 ms 472968 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 1 ms 1100 KB Output is correct
5 Correct 7 ms 6048 KB Output is correct
6 Correct 8 ms 5824 KB Output is correct
7 Correct 4 ms 4676 KB Output is correct
8 Correct 4 ms 4484 KB Output is correct
9 Correct 8 ms 5964 KB Output is correct
10 Correct 4 ms 4556 KB Output is correct
11 Correct 73 ms 101448 KB Output is correct
12 Correct 375 ms 476196 KB Output is correct
13 Correct 322 ms 466316 KB Output is correct
14 Correct 387 ms 476264 KB Output is correct
15 Correct 391 ms 476756 KB Output is correct
16 Correct 373 ms 476128 KB Output is correct
17 Correct 299 ms 462660 KB Output is correct
18 Correct 331 ms 465876 KB Output is correct
19 Correct 350 ms 472260 KB Output is correct
20 Correct 357 ms 472968 KB Output is correct
21 Incorrect 1 ms 204 KB Output isn't correct
22 Halted 0 ms 0 KB -