oj.uz

Submission #520229

# Submission time Handle Problem Language Result Execution time Memory
520229 2022-01-28T23:59:03 Z kevin Skyscraper (JOI16_skyscraper) C++17
20 / 100
 318 ms 72152 KB 
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define nl cout<<"\n"
#define ca(v) for(auto i:v) cout<<i<<" ";

const int MOD = 1e9 + 7;

int dp[102][102][1002][3];

int main()
{
    // ios_base::sync_with_stdio(0); cin.tie(0);
    if (fopen("input.in", "r")) freopen("input.in", "r", stdin);
    int n, l;
    cin>>n>>l;
    int ar[n];
    for(int i=0; i<n; i++) cin>>ar[i];
    if(n == 1) { cout<< 1; return 0; }
    sort(ar, ar+n);
    dp[0][0][0][0] = 1;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            for(int v=0; v<=l; v++){
                for(int r=0; r<3; r++){
                    int d = ar[i] - (i?ar[i-1]:0);
                    int nx = v + d * (j * 2 - r);
                    if(nx > l || nx < 0) continue;
                    // merge 2
                    if(j) dp[i+1][j-1][nx][r] = (dp[i+1][j-1][nx][r] + dp[i][j][v][r] * (j-1) % MOD) % MOD;
                    // add to exsisting
                    dp[i+1][j][nx][r] = (dp[i+1][j][nx][r] + dp[i][j][v][r] * (2*j-r) % MOD) % MOD;
                    // cout<<i+1<<"|"<<j<<"|"<<nx<<"|"<<r<<"|"<<dp[i+1][j][nx][r];
                    // add to exsisting and -1
                    if(r<2) dp[i+1][j][nx][r+1] = (dp[i+1][j][nx][r+1] + dp[i][j][v][r] * (2-r) % MOD) % MOD;
                    // make new
                    dp[i+1][j+1][nx][r] = (dp[i+1][j+1][nx][r] + dp[i][j][v][r] * (j+1-r) % MOD) % MOD;
                    // make new and -1
                    if(r<2) dp[i+1][j+1][nx][r+1] = (dp[i+1][j+1][nx][r+1] + dp[i][j][v][r] * (2-r) % MOD) % MOD;
                }
            }
        }
    }
    int tot = 0;
    for(int i=0; i<=l; i++) tot = (tot + dp[n][1][i][2]) % MOD;
    cout<<tot;
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:15:40: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     if (fopen("input.in", "r")) freopen("input.in", "r", stdin);
      |                                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 432 KB Output is correct
5 Correct 3 ms 844 KB Output is correct
6 Correct 3 ms 844 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 560 KB Output is correct
9 Correct 3 ms 972 KB Output is correct
10 Correct 1 ms 588 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 972 KB Output is correct
2 Correct 2 ms 1076 KB Output is correct
3 Correct 1 ms 1196 KB Output is correct
4 Correct 1 ms 944 KB Output is correct
5 Correct 2 ms 1100 KB Output is correct
6 Correct 2 ms 1228 KB Output is correct
7 Correct 1 ms 940 KB Output is correct
8 Correct 1 ms 1200 KB Output is correct
9 Correct 2 ms 1228 KB Output is correct
10 Correct 1 ms 1072 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 304 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 432 KB Output is correct
5 Correct 3 ms 844 KB Output is correct
6 Correct 3 ms 844 KB Output is correct
7 Correct 1 ms 588 KB Output is correct
8 Correct 1 ms 560 KB Output is correct
9 Correct 3 ms 972 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 1 ms 972 KB Output is correct
12 Correct 2 ms 1076 KB Output is correct
13 Correct 1 ms 1196 KB Output is correct
14 Correct 1 ms 944 KB Output is correct
15 Correct 2 ms 1100 KB Output is correct
16 Correct 2 ms 1228 KB Output is correct
17 Correct 1 ms 940 KB Output is correct
18 Correct 1 ms 1200 KB Output is correct
19 Correct 2 ms 1228 KB Output is correct
20 Correct 1 ms 1072 KB Output is correct
21 Correct 4 ms 4044 KB Output is correct
22 Incorrect 318 ms 72152 KB Output isn't correct
23 Halted 0 ms 0 KB -