oj.uz

Submission #333816

# Submission time Handle Problem Language Result Execution time Memory
333816 2020-12-07T20:29:31 Z nextgenxing Skyscraper (JOI16_skyscraper) C++14
100 / 100
 69 ms 25452 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)%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) if(dp[i][j][k][z]){
        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 0 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 1 ms 620 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 768 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 620 KB Output is correct
3 Correct 1 ms 748 KB Output is correct
4 Correct 1 ms 620 KB Output is correct
5 Correct 1 ms 620 KB Output is correct
6 Correct 1 ms 748 KB Output is correct
7 Correct 1 ms 620 KB Output is correct
8 Correct 1 ms 748 KB Output is correct
9 Correct 1 ms 748 KB Output is correct
10 Correct 1 ms 620 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 0 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 1 ms 620 KB Output is correct
6 Correct 1 ms 620 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 768 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 620 KB Output is correct
13 Correct 1 ms 748 KB Output is correct
14 Correct 1 ms 620 KB Output is correct
15 Correct 1 ms 620 KB Output is correct
16 Correct 1 ms 748 KB Output is correct
17 Correct 1 ms 620 KB Output is correct
18 Correct 1 ms 748 KB Output is correct
19 Correct 1 ms 748 KB Output is correct
20 Correct 1 ms 620 KB Output is correct
21 Correct 2 ms 1408 KB Output is correct
22 Correct 69 ms 25452 KB Output is correct
23 Correct 52 ms 9452 KB Output is correct
24 Correct 51 ms 13548 KB Output is correct
25 Correct 54 ms 10860 KB Output is correct
26 Correct 49 ms 9964 KB Output is correct
27 Correct 25 ms 10476 KB Output is correct
28 Correct 32 ms 12928 KB Output is correct
29 Correct 53 ms 17900 KB Output is correct
30 Correct 54 ms 10860 KB Output is correct