oj.uz

Submission #528030

# Submission time Handle Problem Language Result Execution time Memory
528030 2022-02-19T03:26:05 Z tphuc2908 Skyscraper (JOI16_skyscraper) C++14
20 / 100
 2000 ms 435348 KB 
#include<bits/stdc++.h>

using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#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:33:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |         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 2 ms 3916 KB Output is correct
3 Correct 2 ms 3916 KB Output is correct
4 Correct 3 ms 3948 KB Output is correct
5 Correct 9 ms 5576 KB Output is correct
6 Correct 9 ms 5708 KB Output is correct
7 Correct 8 ms 4940 KB Output is correct
8 Correct 4 ms 4196 KB Output is correct
9 Correct 9 ms 5664 KB Output is correct
10 Correct 4 ms 4172 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4428 KB Output is correct
2 Correct 31 ms 10316 KB Output is correct
3 Correct 8 ms 5196 KB Output is correct
4 Correct 31 ms 10488 KB Output is correct
5 Correct 40 ms 11868 KB Output is correct
6 Correct 23 ms 7784 KB Output is correct
7 Correct 12 ms 6172 KB Output is correct
8 Correct 8 ms 5196 KB Output is correct
9 Correct 11 ms 5324 KB Output is correct
10 Correct 29 ms 9260 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 2 ms 3916 KB Output is correct
3 Correct 2 ms 3916 KB Output is correct
4 Correct 3 ms 3948 KB Output is correct
5 Correct 9 ms 5576 KB Output is correct
6 Correct 9 ms 5708 KB Output is correct
7 Correct 8 ms 4940 KB Output is correct
8 Correct 4 ms 4196 KB Output is correct
9 Correct 9 ms 5664 KB Output is correct
10 Correct 4 ms 4172 KB Output is correct
11 Correct 5 ms 4428 KB Output is correct
12 Correct 31 ms 10316 KB Output is correct
13 Correct 8 ms 5196 KB Output is correct
14 Correct 31 ms 10488 KB Output is correct
15 Correct 40 ms 11868 KB Output is correct
16 Correct 23 ms 7784 KB Output is correct
17 Correct 12 ms 6172 KB Output is correct
18 Correct 8 ms 5196 KB Output is correct
19 Correct 11 ms 5324 KB Output is correct
20 Correct 29 ms 9260 KB Output is correct
21 Correct 378 ms 72912 KB Output is correct
22 Execution timed out 2096 ms 435348 KB Time limit exceeded
23 Halted 0 ms 0 KB -