oj.uz

Submission #91274

# Submission time Handle Problem Language Result Execution time Memory
91274 2018-12-26T21:23:17 Z RezwanArefin01 Skyscraper (JOI16_skyscraper) C++17
15 / 100
 99 ms 120476 KB 
///usr/bin/g++ -O2 $0 -o ${0%.cpp} && echo "----------" && ./${0%.cpp}; exit;
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> ii; 

const int mod = 1e9 + 7; 
int a[101], n, L; 
int dp[101][101][3][1001]; 

void add(int &a, int b) { if((a += b) >= mod) a -= mod; }
#define mul(a, b) ((ll)(a) * (b) % mod)

int f(int i, int c, int e, int cost) {
    cost += (a[i] - a[i - 1]) * (2 * c + e); 
    if(c < 0 || e > 2 || cost > L) return 0;
    if(i == n) return c == 0 && e;

    int &ret = dp[i][c][e][cost]; 
    if(~ret) return ret; 
    ret = 0;
    
    add(ret, mul(c + 1, f(i + 1, c + 1, e, cost))); 
    add(ret, mul(c + e - 1, f(i + 1, c - 1, e, cost))); 
    add(ret, mul(2 * c + e, f(i + 1, c, e, cost))); 
    add(ret, mul(2 - e, f(i + 1, c, e + 1, cost))); 
    add(ret, mul(2 - e, f(i + 1, c - 1, e + 1, cost))); 

    return ret; 

}
int main() {
    scanf("%d %d", &n, &L); 
    for(int i = 1; i <= n; i++) 
        scanf("%d", &a[i]); 
    sort(a + 1, a + n + 1); 
    memset(dp, -1, sizeof dp); 
    printf("%d\n", f(1, 0, 0, 0)); 
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:34:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d", &n, &L); 
     ~~~~~^~~~~~~~~~~~~~~~~
skyscraper.cpp:36:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &a[i]); 
         ~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 95 ms 120184 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 99 ms 120320 KB Output is correct
2 Correct 93 ms 120376 KB Output is correct
3 Correct 95 ms 120436 KB Output is correct
4 Correct 80 ms 120436 KB Output is correct
5 Correct 80 ms 120476 KB Output is correct
6 Correct 80 ms 120476 KB Output is correct
7 Correct 79 ms 120476 KB Output is correct
8 Correct 90 ms 120476 KB Output is correct
9 Correct 83 ms 120476 KB Output is correct
10 Correct 92 ms 120476 KB Output is correct

Subtask #3
0 / 80.0

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