oj.uz

Submission #844623

# Submission time Handle Problem Language Result Execution time Memory
844623 2023-09-05T14:50:57 Z rukashii Skyscraper (JOI16_skyscraper) C++17
100 / 100
 94 ms 91984 KB 
#include <bits/stdc++.h>
using namespace std;

#define file  if (fopen("input.txt", "r")) { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); }
#define int long long

void setIn(string s) { freopen(s.c_str(),"r",stdin); }
void setOut(string s) { freopen(s.c_str(),"w",stdout); }
void setIO(string s = "") {
    if (s.size()) setIn(s+".in"), setOut(s+".out");
}

const int maxn = 102, maxl = 2002, lim = 2000, add = 2000, MOD = 1e9 + 7;

int n, L, a[maxn], dp[maxn][maxn][maxl][3];

signed main()
{
    // setIO();
    file;
    ios::sync_with_stdio(0); cin.tie(0);

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

    if (n == 1)
        return cout << 1, 0;
    
    sort(a + 1, a + 1 + n);
    
    dp[1][1][0][0] = 1;
    dp[1][1][0][1] = 2;

    for (int i = 2; i <= n; i++)
        for (int j = 1; j < i; j++)
        {
            for (int cost = 0; cost <= L; cost++)
            {
                for (int e = 0; e <= 2; e++)
                {
                    // let's say we have the initial permutation with empty spot replaced by a[i - 1]
                    // so we have the initial cost
                    // if we want to update the newcost for next i, we must add exactly (a[i] - a[i - 1]) * (2 * j - e)
                    int nc = cost + (a[i] - a[i - 1]) * (2 * j - e);

                    if (nc > L)
                        continue;
                    
                    //add new component in mid
                    (dp[i][j + 1][nc][e] += dp[i - 1][j][cost][e] * (j - e + 1)) %= MOD;
                    //add new component in the end || top
                    (dp[i][j + 1][nc][e + 1] += dp[i - 1][j][cost][e] * (2 - e)) %= MOD;
                    //append to end || top of a component (not ending or starting)
                    (dp[i][j][nc][e] += dp[i - 1][j][cost][e] * (2 * j - e));
                    //append to end || top
                    (dp[i][j][nc][e + 1] += dp[i - 1][j][cost][e] * (2 - e)) %= MOD;
                    //merge 2 components
                    (dp[i][j - 1][nc][e] += dp[i - 1][j][cost][e] * (j - 1)) %= MOD;
                }
            }
        } 

    int ans = 0;
    for (int i = 0; i <= L; i++)
        ans += dp[n][1][i][2], ans %= MOD;
    
    cout << ans;
}

Compilation message

skyscraper.cpp: In function 'void setIn(std::string)':
skyscraper.cpp:7:31: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    7 | void setIn(string s) { freopen(s.c_str(),"r",stdin); }
      |                        ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp: In function 'void setOut(std::string)':
skyscraper.cpp:8:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    8 | void setOut(string s) { freopen(s.c_str(),"w",stdout); }
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp: In function 'int main()':
skyscraper.cpp:4:53: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    4 | #define file  if (fopen("input.txt", "r")) { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); }
      |                                              ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:20:5: note: in expansion of macro 'file'
   20 |     file;
      |     ^~~~
skyscraper.cpp:4:87: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
    4 | #define file  if (fopen("input.txt", "r")) { freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); }
      |                                                                                ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:20:5: note: in expansion of macro 'file'
   20 |     file;
      |     ^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2648 KB Output is correct
5 Correct 1 ms 3160 KB Output is correct
6 Correct 1 ms 3160 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 1 ms 2904 KB Output is correct
9 Correct 2 ms 3160 KB Output is correct
10 Correct 2 ms 2656 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4952 KB Output is correct
2 Correct 1 ms 4952 KB Output is correct
3 Correct 1 ms 4952 KB Output is correct
4 Correct 1 ms 4952 KB Output is correct
5 Correct 1 ms 4952 KB Output is correct
6 Correct 1 ms 5208 KB Output is correct
7 Correct 1 ms 4956 KB Output is correct
8 Correct 2 ms 4952 KB Output is correct
9 Correct 1 ms 5208 KB Output is correct
10 Correct 2 ms 4952 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2396 KB Output is correct
4 Correct 1 ms 2648 KB Output is correct
5 Correct 1 ms 3160 KB Output is correct
6 Correct 1 ms 3160 KB Output is correct
7 Correct 1 ms 2648 KB Output is correct
8 Correct 1 ms 2904 KB Output is correct
9 Correct 2 ms 3160 KB Output is correct
10 Correct 2 ms 2656 KB Output is correct
11 Correct 1 ms 4952 KB Output is correct
12 Correct 1 ms 4952 KB Output is correct
13 Correct 1 ms 4952 KB Output is correct
14 Correct 1 ms 4952 KB Output is correct
15 Correct 1 ms 4952 KB Output is correct
16 Correct 1 ms 5208 KB Output is correct
17 Correct 1 ms 4956 KB Output is correct
18 Correct 2 ms 4952 KB Output is correct
19 Correct 1 ms 5208 KB Output is correct
20 Correct 2 ms 4952 KB Output is correct
21 Correct 3 ms 9816 KB Output is correct
22 Correct 74 ms 75440 KB Output is correct
23 Correct 94 ms 90716 KB Output is correct
24 Correct 83 ms 85392 KB Output is correct
25 Correct 94 ms 91728 KB Output is correct
26 Correct 84 ms 82768 KB Output is correct
27 Correct 38 ms 49744 KB Output is correct
28 Correct 45 ms 56416 KB Output is correct
29 Correct 76 ms 82512 KB Output is correct
30 Correct 94 ms 91984 KB Output is correct