제출 #844623

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
844623		rukashii	Skyscraper (JOI16_skyscraper)	C++17	100 / 100	94 ms	91984 KiB

skyscraper

#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;
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 5
• Subtask 2: 15 / 15
• Subtask 3: 80 / 80