oj.uz

Submission #528033

# Submission time Handle Problem Language Result Execution time Memory
528033 2022-02-19T03:26:51 Z tphuc2908 Skyscraper (JOI16_skyscraper) C++14
20 / 100
 2000 ms 226752 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;
}

map<int,int> f[N][N][3];
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 3404 KB Output is correct
2 Correct 2 ms 3404 KB Output is correct
3 Correct 2 ms 3348 KB Output is correct
4 Correct 3 ms 3532 KB Output is correct
5 Correct 10 ms 5196 KB Output is correct
6 Correct 11 ms 5464 KB Output is correct
7 Correct 8 ms 4444 KB Output is correct
8 Correct 3 ms 3660 KB Output is correct
9 Correct 12 ms 5344 KB Output is correct
10 Correct 4 ms 3788 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 4044 KB Output is correct
2 Correct 55 ms 10460 KB Output is correct
3 Correct 11 ms 4840 KB Output is correct
4 Correct 80 ms 10456 KB Output is correct
5 Correct 72 ms 12120 KB Output is correct
6 Correct 35 ms 7628 KB Output is correct
7 Correct 22 ms 5868 KB Output is correct
8 Correct 12 ms 4812 KB Output is correct
9 Correct 12 ms 4940 KB Output is correct
10 Correct 44 ms 9156 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3404 KB Output is correct
2 Correct 2 ms 3404 KB Output is correct
3 Correct 2 ms 3348 KB Output is correct
4 Correct 3 ms 3532 KB Output is correct
5 Correct 10 ms 5196 KB Output is correct
6 Correct 11 ms 5464 KB Output is correct
7 Correct 8 ms 4444 KB Output is correct
8 Correct 3 ms 3660 KB Output is correct
9 Correct 12 ms 5344 KB Output is correct
10 Correct 4 ms 3788 KB Output is correct
11 Correct 5 ms 4044 KB Output is correct
12 Correct 55 ms 10460 KB Output is correct
13 Correct 11 ms 4840 KB Output is correct
14 Correct 80 ms 10456 KB Output is correct
15 Correct 72 ms 12120 KB Output is correct
16 Correct 35 ms 7628 KB Output is correct
17 Correct 22 ms 5868 KB Output is correct
18 Correct 12 ms 4812 KB Output is correct
19 Correct 12 ms 4940 KB Output is correct
20 Correct 44 ms 9156 KB Output is correct
21 Correct 720 ms 79568 KB Output is correct
22 Execution timed out 2098 ms 226752 KB Time limit exceeded
23 Halted 0 ms 0 KB -