oj.uz

Submission #844620

# Submission time Handle Problem Language Result Execution time Memory
844620 2023-09-05T14:43:53 Z rukashii Skyscraper (JOI16_skyscraper) C++17
15 / 100
 2 ms 3164 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 = 1002, 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];
    
    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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2512 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2908 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 3164 KB Output is correct
4 Correct 1 ms 3160 KB Output is correct
5 Correct 2 ms 3164 KB Output is correct
6 Correct 2 ms 3160 KB Output is correct
7 Correct 1 ms 2904 KB Output is correct
8 Correct 1 ms 3164 KB Output is correct
9 Correct 1 ms 3164 KB Output is correct
10 Correct 1 ms 2904 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 2512 KB Output isn't correct
2 Halted 0 ms 0 KB -