oj.uz

Submission #528029

# Submission time Handle Problem Language Result Execution time Memory
528029 2022-02-19T03:24:20 Z tphuc2908 Skyscraper (JOI16_skyscraper) C++14
20 / 100
 2000 ms 426312 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 = 1e2 + 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];
    sort(a + 1, a + n + 1);
}

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;
}

unordered_map<int,int> f[N][N][3];
unordered_set<int> s[N][N][3];

void process(){
    f[1][1][0][-2*a[1]] = 1;
    f[1][1][1][-a[1]] = 2;
    f[1][1][2][0] = 1;
    s[1][1][0].insert(-2*a[1]);
    s[1][1][1].insert(-a[1]);
    s[1][1][2].insert(0);
    for(int i = 1; i < n; ++i){
        for(int j = 1; j <= i; ++j){
            for(int t = 0; t <= 2; ++t){
                for(int sum : s[i][j][t]){
                    if(j >= 2){
                        // merge two cc
                        f[i + 1][j - 1][t][sum + 2*a[i + 1]] = add(f[i + 1][j - 1][t][sum + 2*a[i + 1]], mul(f[i][j][t][sum], j - 1));
                        s[i + 1][j - 1][t].insert(sum + 2*a[i + 1]);
                    }
                    if(t==0){ // not having any at the end or beginning
                        // new cc
                        f[i + 1][j + 1][0][sum + -2*a[i + 1]] = add(f[i + 1][j + 1][0][sum + -2*a[i + 1]], mul(f[i][j][t][sum], j + 1));
                        f[i + 1][j + 1][1][sum + -a[i + 1]] = add(f[i + 1][j + 1][1][sum + -a[i + 1]], mul(f[i][j][t][sum], 2)); // new cc but at the end or beginning
                        s[i + 1][j + 1][0].insert(sum - 2*a[i + 1]);
                        s[i + 1][j + 1][1].insert(sum - a[i + 1]);
                        // attach to existing cc
                        f[i + 1][j][0][sum] = add(f[i + 1][j][0][sum], mul(f[i][j][t][sum], 2*j));
                        s[i + 1][j][0].insert(sum);
                        f[i + 1][j][1][sum + a[i + 1]] = add(f[i + 1][j][1][sum + a[i + 1]], mul(f[i][j][t][sum], 2)); // increasing one endpoint
                        s[i + 1][j][1].insert(sum + a[i + 1]);
                    }
                    else if(t==1){
                            // new cc
                            f[i + 1][j + 1][1][sum -2*a[i + 1]] = add(f[i + 1][j + 1][1][sum - 2*a[i + 1]], mul(f[i][j][t][sum], j));
                            f[i + 1][j + 1][2][sum - a[i + 1]] = add(f[i + 1][j + 1][2][sum - a[i + 1]], f[i][j][t][sum]); // new cc but at one endpoint
                            s[i + 1][j + 1][1].insert(sum - 2*a[i + 1]);
                            s[i + 1][j + 1][2].insert(sum - a[i + 1]);
                            // attach to existing cc
                            f[i + 1][j][1][sum] = add(f[i + 1][j][1][sum], mul(f[i][j][t][sum], 2*j - 1));
                            f[i + 1][j][2][sum + a[i + 1]] = add(f[i + 1][j][2][sum + a[i + 1]], f[i][j][t][sum]); // increasing one endpoint to two endpoints
                            s[i + 1][j][1].insert(sum);
                            s[i + 1][j][2].insert(sum + a[i + 1]);
                        }
                        else{
                            if(j >= 2){
                                // new cc
                                f[i + 1][j + 1][2][sum - 2*a[i + 1]] = add(f[i + 1][j + 1][2][sum - 2*a[i + 1]], mul(f[i][j][t][sum], j - 1));
                                s[i + 1][j + 1][2].insert(sum - 2*a[i + 1]);
                                // attach to existing cc
                                f[i + 1][j][2][sum] = add(f[i + 1][j][2][sum], mul(f[i][j][t][sum], 2*j - 2));
                                s[i + 1][j][2].insert(sum);
                            }
                        }
                }
            }
        }
    }
    int res = 0;
    for(int i = 0; i <= L; ++i)
        res = add(res, f[n][1][2][i]);
    cout << res;
}

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 2 ms 3916 KB Output is correct
2 Correct 3 ms 3936 KB Output is correct
3 Correct 3 ms 3936 KB Output is correct
4 Correct 3 ms 4044 KB Output is correct
5 Correct 8 ms 5580 KB Output is correct
6 Correct 8 ms 5708 KB Output is correct
7 Correct 6 ms 4940 KB Output is correct
8 Correct 4 ms 4200 KB Output is correct
9 Correct 8 ms 5708 KB Output is correct
10 Correct 4 ms 4300 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4456 KB Output is correct
2 Correct 30 ms 10332 KB Output is correct
3 Correct 9 ms 5196 KB Output is correct
4 Correct 31 ms 10412 KB Output is correct
5 Correct 40 ms 11896 KB Output is correct
6 Correct 20 ms 7804 KB Output is correct
7 Correct 14 ms 6220 KB Output is correct
8 Correct 8 ms 5216 KB Output is correct
9 Correct 8 ms 5324 KB Output is correct
10 Correct 26 ms 9156 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3916 KB Output is correct
2 Correct 3 ms 3936 KB Output is correct
3 Correct 3 ms 3936 KB Output is correct
4 Correct 3 ms 4044 KB Output is correct
5 Correct 8 ms 5580 KB Output is correct
6 Correct 8 ms 5708 KB Output is correct
7 Correct 6 ms 4940 KB Output is correct
8 Correct 4 ms 4200 KB Output is correct
9 Correct 8 ms 5708 KB Output is correct
10 Correct 4 ms 4300 KB Output is correct
11 Correct 5 ms 4456 KB Output is correct
12 Correct 30 ms 10332 KB Output is correct
13 Correct 9 ms 5196 KB Output is correct
14 Correct 31 ms 10412 KB Output is correct
15 Correct 40 ms 11896 KB Output is correct
16 Correct 20 ms 7804 KB Output is correct
17 Correct 14 ms 6220 KB Output is correct
18 Correct 8 ms 5216 KB Output is correct
19 Correct 8 ms 5324 KB Output is correct
20 Correct 26 ms 9156 KB Output is correct
21 Correct 390 ms 72992 KB Output is correct
22 Execution timed out 2082 ms 426312 KB Time limit exceeded
23 Halted 0 ms 0 KB -