oj.uz

Submission #57174

# Submission time Handle Problem Language Result Execution time Memory
57174 2018-07-14T08:13:55 Z 강태규(#1651) Skyscraper (JOI16_skyscraper) C++11
20 / 100
 130 ms 65004 KB 
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
#include <set>
#include <map>
#include <unordered_map>
#include <functional>
#include <cstring>
#include <cmath>
#include <ctime>
#include <cstdlib>

using namespace std;
typedef long long llong;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<llong, llong> pll;

int popcount(int x) {
    int ret = 0;
    while (x) {
        ret += x & 1;
        x >>= 1;
    }
    return ret;
}

int difcount(int x, int n) {
    int ret = 0;
    for (int i = 1; i < n; ++i) {
        ret += ((x >> i) & 1) ^ ((x >> (i - 1) & 1));
    }
    return ret;
}

const int mod = 1e9 + 7;
int n, l;
int a[101];
int dp[1 << 14][1001];
vector<int> cs[15];
int dif[1 << 14];
int main() {
    scanf("%d%d", &n, &l);
    if (n > 15) return 0;
    for (int i = 0; i < (1 << n); ++i) {
        cs[popcount(i)].push_back(i);
        dif[i] = difcount(i, n);
    }
    for (int i = 1; i <= n; ++i) {
        scanf("%d", a + i);
    }
    sort(a + 1, a + (n + 1));
    dp[0][0] = 1;
    for (int it = 0; it < 14; ++it) {
        for (int i : cs[it]) {
            for (int j = 0; j < 14; ++j) {
                if ((i >> j) & 1) continue;
                for (int k = 0; k <= l; ++k) {
                    int d = k + dif[i] * (a[it + 1] - a[it]);
                    if (l < d) continue;
                    dp[i | (1 << j)][d] += dp[i][k];
                    dp[i | (1 << j)][d] %= mod;
                }
            }
        }
    }
    int ret = 0;
    for (int i = 0; i <= l; ++i) {
        ret += dp[(1 << n) - 1][i];
        ret %= mod;
    }
    printf("%d\n", ret);
	return 0;
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:45: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:52:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", a + i);
         ~~~~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 2 ms 776 KB Output is correct
4 Correct 4 ms 2644 KB Output is correct
5 Correct 17 ms 7528 KB Output is correct
6 Correct 14 ms 7528 KB Output is correct
7 Correct 10 ms 7528 KB Output is correct
8 Correct 11 ms 7576 KB Output is correct
9 Correct 16 ms 7576 KB Output is correct
10 Correct 12 ms 7576 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 48664 KB Output is correct
2 Correct 103 ms 63768 KB Output is correct
3 Correct 95 ms 64828 KB Output is correct
4 Correct 100 ms 64828 KB Output is correct
5 Correct 111 ms 64828 KB Output is correct
6 Correct 119 ms 64832 KB Output is correct
7 Correct 101 ms 64832 KB Output is correct
8 Correct 115 ms 64832 KB Output is correct
9 Correct 130 ms 65004 KB Output is correct
10 Correct 110 ms 65004 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 2 ms 776 KB Output is correct
4 Correct 4 ms 2644 KB Output is correct
5 Correct 17 ms 7528 KB Output is correct
6 Correct 14 ms 7528 KB Output is correct
7 Correct 10 ms 7528 KB Output is correct
8 Correct 11 ms 7576 KB Output is correct
9 Correct 16 ms 7576 KB Output is correct
10 Correct 12 ms 7576 KB Output is correct
11 Correct 63 ms 48664 KB Output is correct
12 Correct 103 ms 63768 KB Output is correct
13 Correct 95 ms 64828 KB Output is correct
14 Correct 100 ms 64828 KB Output is correct
15 Correct 111 ms 64828 KB Output is correct
16 Correct 119 ms 64832 KB Output is correct
17 Correct 101 ms 64832 KB Output is correct
18 Correct 115 ms 64832 KB Output is correct
19 Correct 130 ms 65004 KB Output is correct
20 Correct 110 ms 65004 KB Output is correct
21 Incorrect 2 ms 65004 KB Output isn't correct
22 Halted 0 ms 0 KB -