oj.uz

Submission #104700

# Submission time Handle Problem Language Result Execution time Memory
104700 2019-04-09T00:21:40 Z the_art_of_war Skyscraper (JOI16_skyscraper) C++14
100 / 100
 374 ms 164088 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int inf_int = 1e9 + 100;
const ll inf_ll = 8e18;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double dbl;
#define pb push_back
const double pi = 3.1415926535898;
#define dout if(debug) cout
#define fi first
#define se second
#define sp setprecision
#define sz(a) (int(a.size()))
#define all(a) a.begin(),a.end()
bool debug = 0;
const int MAXN = 1e5 + 100;
const int LOG = 20;
const int mod = 1e9 + 7;
const int MX = 1e6 + 100;
typedef long long li;
const li MOD = 1000000000949747713ll;

int N,L;

int dp[101][1024][101][2][2];
int a[101];
ll get(int i,int cur_cost, int comp,int l,int r) {
    if(cur_cost > L)
        return 0;
    if(comp < 0)
        return 0;

    int next_cost = cur_cost;
    if(i > 0){
        next_cost += (a[i] - a[i-1] ) * (2*comp + l + r);
    }
    if(next_cost > L)
        return 0;
    if(i==N-1) {
        if(comp == 0)
            return 1;
        return 0;
    }


    if(dp[i][cur_cost][comp][l][r] != -1)
        return dp[i][cur_cost][comp][l][r];

    ll res = 0;
    res+=get(i+1,next_cost,comp-1,1,r) * comp; //left
    res+=get(i+1,next_cost,comp,1,r); //left

    res+=get(i+1,next_cost,comp-1,l,1) * comp; // right
    res+=get(i+1,next_cost,comp,l,1); // right

    res+=get(i+1,next_cost,comp+1,l,r); //new

    res+=get(i+1,next_cost,comp,l,r) * comp * 2; // to middle

    res+=get(i+1,next_cost,comp-1,l,r) * comp * (comp - 1);

    if(res)
    dout << i <<" "<<cur_cost <<" "<<comp <<" "<<l<<" "<<r<<" - "<<res<<endl;

    return dp[i][cur_cost][comp][l][r] = res%mod;
}

void solve() {
   memset(dp,-1,sizeof dp);
   cin >> N >> L;
   for(int i=0;i<N;++i){
       cin >> a[i];
   }
   sort(a,a+N);
   cout << get(0,0,0,0,0)<<"\n";

}

signed main() {
#ifdef zxc
    debug = 1;
    freopen("../input.txt", "r", stdin);
#else

#endif //zxc
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout.setf(ios::fixed);
    cout.precision(20);

    int t = 1;

     while (t--)
         solve();
    dout << (1.0 * clock() / CLOCKS_PER_SEC)<<endl;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 163892 KB Output is correct
2 Correct 135 ms 163832 KB Output is correct
3 Correct 131 ms 163960 KB Output is correct
4 Correct 136 ms 163880 KB Output is correct
5 Correct 128 ms 163960 KB Output is correct
6 Correct 132 ms 163860 KB Output is correct
7 Correct 128 ms 163932 KB Output is correct
8 Correct 131 ms 164088 KB Output is correct
9 Correct 124 ms 163828 KB Output is correct
10 Correct 153 ms 163996 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 163932 KB Output is correct
2 Correct 132 ms 163932 KB Output is correct
3 Correct 135 ms 164060 KB Output is correct
4 Correct 141 ms 163832 KB Output is correct
5 Correct 128 ms 163832 KB Output is correct
6 Correct 145 ms 163864 KB Output is correct
7 Correct 134 ms 163824 KB Output is correct
8 Correct 131 ms 163888 KB Output is correct
9 Correct 126 ms 163888 KB Output is correct
10 Correct 136 ms 163960 KB Output is correct

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 146 ms 163892 KB Output is correct
2 Correct 135 ms 163832 KB Output is correct
3 Correct 131 ms 163960 KB Output is correct
4 Correct 136 ms 163880 KB Output is correct
5 Correct 128 ms 163960 KB Output is correct
6 Correct 132 ms 163860 KB Output is correct
7 Correct 128 ms 163932 KB Output is correct
8 Correct 131 ms 164088 KB Output is correct
9 Correct 124 ms 163828 KB Output is correct
10 Correct 153 ms 163996 KB Output is correct
11 Correct 138 ms 163932 KB Output is correct
12 Correct 132 ms 163932 KB Output is correct
13 Correct 135 ms 164060 KB Output is correct
14 Correct 141 ms 163832 KB Output is correct
15 Correct 128 ms 163832 KB Output is correct
16 Correct 145 ms 163864 KB Output is correct
17 Correct 134 ms 163824 KB Output is correct
18 Correct 131 ms 163888 KB Output is correct
19 Correct 126 ms 163888 KB Output is correct
20 Correct 136 ms 163960 KB Output is correct
21 Correct 135 ms 163884 KB Output is correct
22 Correct 365 ms 163928 KB Output is correct
23 Correct 374 ms 163832 KB Output is correct
24 Correct 335 ms 163912 KB Output is correct
25 Correct 324 ms 163960 KB Output is correct
26 Correct 288 ms 163960 KB Output is correct
27 Correct 174 ms 164008 KB Output is correct
28 Correct 212 ms 164028 KB Output is correct
29 Correct 268 ms 163960 KB Output is correct
30 Correct 327 ms 164040 KB Output is correct