oj.uz

Submission #333814

# Submission time Handle Problem Language Result Execution time Memory
333814 2020-12-07T20:28:13 Z nextgenxing Skyscraper (JOI16_skyscraper) C++14
20 / 100
 146 ms 67348 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define FOR(i, a, b) for(int i = (a); i < (b); i++)
#define F0R(i, x) FOR(i, 0, x)
const int MAX_N = 102;
const int MAX_L = 1002;
const ll MOD = 1000000007;

void setIO(string name = "skyscraper") {
    ios_base::sync_with_stdio(0); cin.tie(0);
    freopen((name+".in").c_str(), "r", stdin);
    freopen((name+".out").c_str(), "w", stdout);
}

ll ad(ll& a, ll b, ll mod = MOD){
    a = a+b; if(a >= mod) a -= mod;
    return a;
}

int n, l;
ll dp[MAX_N][MAX_N][MAX_L][3], a[MAX_N];

int main(int argc, const char * argv[]) {
//    setIO();
    cin >> n >> l; F0R(i, n) cin >> a[i];
    sort(a, a+n), a[n] = 10001;
    if(n == 1){ cout << 1 << endl; return 0; }
    if(a[1]-a[0] <= l) dp[1][1][a[1]-a[0]][1] = 2;
    if(2*(a[1]-a[0]) <= l) dp[1][1][2*(a[1]-a[0])][0] = 1;
    FOR(i, 1, n) FOR(j, 1, i+1) F0R(k, l+1) F0R(z, 3){
        int d = a[i+1]-a[i];
        // add to end
        if(z < 2 && k+d*(2*j-z-1) <= l) ad(dp[i+1][j][k+d*(2*j-z-1)][z+1], (2-z)*dp[i][j][k][z]); // add to cc
        if(z < 2 && k+d*(2*j-z+1) <= l) ad(dp[i+1][j+1][k+d*(2*j-z+1)][z+1], (2-z)*dp[i][j][k][z]); // make new cc
        // add to middle
        if(k+d*(2*j-z) <= l) ad(dp[i+1][j][k+d*(2*j-z)][z], (2*j-z)*dp[i][j][k][z]); // add to cc
        if(k+d*(2*j-z+2) <= l) ad(dp[i+1][j+1][k+d*(2*j-z+2)][z], (j-z+1)*dp[i][j][k][z]); // make new cc
        if(j && k+d*(2*j-z-2) <= l) ad(dp[i+1][j-1][k+d*(2*j-z-2)][z], (j-1)*dp[i][j][k][z]); // merge 2 ccs
    }
    ll ans = 0; F0R(i, l+1) ad(ans, dp[n][1][i][2]);
    cout << ans << endl;
    return 0;
}

Compilation message

skyscraper.cpp: In function 'void setIO(std::string)':
skyscraper.cpp:13:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   13 |     freopen((name+".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:14:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   14 |     freopen((name+".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 2 ms 1132 KB Output is correct
6 Correct 1 ms 1004 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 2 ms 1132 KB Output is correct
10 Correct 1 ms 620 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 748 KB Output is correct
2 Correct 1 ms 876 KB Output is correct
3 Correct 1 ms 876 KB Output is correct
4 Correct 1 ms 876 KB Output is correct
5 Correct 1 ms 876 KB Output is correct
6 Correct 1 ms 1004 KB Output is correct
7 Correct 1 ms 748 KB Output is correct
8 Correct 1 ms 876 KB Output is correct
9 Correct 1 ms 1004 KB Output is correct
10 Correct 1 ms 876 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 2 ms 1132 KB Output is correct
6 Correct 1 ms 1004 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 1 ms 620 KB Output is correct
9 Correct 2 ms 1132 KB Output is correct
10 Correct 1 ms 620 KB Output is correct
11 Correct 1 ms 748 KB Output is correct
12 Correct 1 ms 876 KB Output is correct
13 Correct 1 ms 876 KB Output is correct
14 Correct 1 ms 876 KB Output is correct
15 Correct 1 ms 876 KB Output is correct
16 Correct 1 ms 1004 KB Output is correct
17 Correct 1 ms 748 KB Output is correct
18 Correct 1 ms 876 KB Output is correct
19 Correct 1 ms 1004 KB Output is correct
20 Correct 1 ms 876 KB Output is correct
21 Correct 4 ms 3328 KB Output is correct
22 Incorrect 146 ms 67348 KB Output isn't correct
23 Halted 0 ms 0 KB -