oj.uz

Submission #1075320

# Submission time Handle Problem Language Result Execution time Memory
1075320 2024-08-26T02:22:10 Z Boycl07 Skyscraper (JOI16_skyscraper) C++17
100 / 100
 70 ms 3420 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;

#define rep(i, n) for(int i = 1; (i) <= (n); ++i)
#define forn(i, l, r) for(int i = (l); i <= (r); ++i)
#define ford(i, r, l) for(int i = (r); i >= (l); --i)
#define FOR(i, n) for(int i = 0; i < (n); ++i)
#define FORD(i, n) for(int i = ((n) - 1); i >= 0; --i)
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pb push_back
#define endl "\n"
#define task "BAI1"
#define sz(a) int(a.size())
#define C(x, y) make_pair(x, y)
#define all(a) (a).begin(), (a).end()
#define bit(i, mask) (mask >> i & 1)

template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }

inline int readInt()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();int n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline ll readLong()       {char c;while(c=getchar(),c!='-'&&(c<'0'||c>'9'));bool sign=(c=='-');if(sign)c=getchar();ll  n=c-'0';while(c=getchar(),c>='0'&&c<='9')n=10*n+c-'0';return(!sign)?n:-n;}
inline string readString() {char c;while(c=getchar(),c==' '||c=='\n'||c=='\t');string s({c});while(c=getchar(),c!=EOF&&c!=' '&&c!='\n'&&c!='\t')s+=c;return s;}

const int N = 1e2 + 3;
const int M = 1e3 + 3;
const int LOG = 50;
const int MOD = 1e9 + 7;
const ll INF = 1e18;

int n, L;

int dp[2][N][M][4];
int a[N];
void add(int &x, int y)
{
    x += y;
    if(x >= MOD) x -= MOD;
}

int mul(int x, int y) {return 1ll * x * y % MOD;}

void solve()
{
    cin >> n >> L;
    rep(i, n) cin >> a[i];
    if(n == 1) return cout << 1, void();
    sort(a + 1, a + 1 + n);
    int f = 0;
    dp[0][1][0][0] = 1;
    dp[0][1][0][1] = 2;
    forn(i, 2, n)
    {
        for(int num_cc = 1; num_cc <= n; ++num_cc)
            for(int sum = 0; sum <= L; ++sum)
                for(int num_ends = 0; num_ends <= 2; ++num_ends) dp[f ^ 1][num_cc][sum][num_ends] = 0;

        for(int num_cc = 1; num_cc <= n; ++num_cc)
            for(int sum = 0; sum <= L; ++sum)
                for(int num_ends = 0; num_ends <= 2; ++num_ends)
                if(dp[f][num_cc][sum][num_ends]) {
                    int new_sum = sum + 1ll * (a[i] - a[i - 1]) * (2 * num_cc - num_ends);
                    if(new_sum <= L)
                    {
                        #define trans(x, y, z) add(dp[f ^ 1][num_cc + x][new_sum][num_ends + y], mul(dp[f][num_cc][sum][num_ends], z));


                        trans(-1, 0, num_cc - 1); /// merge cc
                        trans(1, 0, num_cc + 1 - num_ends); /// create cc

                        trans(0, 0, 2 * num_cc - num_ends); /// append cc

                        trans(1, 1, 2 - num_ends); /// create end
                        trans(0, 1, 2 - num_ends); /// append end
                    }
                }
        f ^= 1;
    }

    int res = 0;
    for(int sum = 0; sum <= L; ++sum) add(res, dp[f][1][sum][2]);
    cout << res;
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int TC = 1;

    if(fopen("note.inp", "r"))
    {
        freopen("note.inp", "r", stdin);
        freopen("note.out", "w", stdout);
    }

    while(TC--)
    {
        solve();
        cout << endl;
    }

    return 0;
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:100:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  100 |         freopen("note.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:101:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  101 |         freopen("note.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 464 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 0 ms 348 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 608 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 0 ms 464 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 1 ms 604 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 464 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 608 KB Output is correct
13 Correct 0 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 0 ms 464 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 604 KB Output is correct
19 Correct 0 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 2 ms 604 KB Output is correct
22 Correct 35 ms 2924 KB Output is correct
23 Correct 70 ms 3420 KB Output is correct
24 Correct 61 ms 3420 KB Output is correct
25 Correct 38 ms 3416 KB Output is correct
26 Correct 35 ms 3416 KB Output is correct
27 Correct 15 ms 1880 KB Output is correct
28 Correct 16 ms 2136 KB Output is correct
29 Correct 30 ms 2908 KB Output is correct
30 Correct 47 ms 3420 KB Output is correct