oj.uz

Submission #92887

# Submission time Handle Problem Language Result Execution time Memory
92887 2019-01-05T12:26:01 Z LittleFlowers__ Skyscraper (JOI16_skyscraper) C++14
20 / 100
 369 ms 194680 KB 
#include <bits/stdc++.h>
#define bit(x,i) (1&(x>>(i-1)))
#define on(x,i)  (x|(1<<(i-1)))
using namespace std;
const int M=1e9+7;
int n,l,kq;
int a[15];
int f[1<<15][15][210];
int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  cin>>n>>l;
  for(int i=1;i<=n;++i) cin>>a[i];
  if(n<=8)
  {
      sort(a+1,a+n+1);
      do
      {
        int sum=0;
        for(int i=1;i<n;++i) sum+=abs(a[i]-a[i+1]);
        kq+=sum<=l;
      }
      while(next_permutation(a+1,a+n+1));
      return cout<<kq,0;
  }
  f[0][0][0]=1;
  for(int tt=0;tt<(1<<n)-1;++tt) for(int i=0;i<=n;++i) for(int t=0;t<=l;++t) if(f[tt][i][t])
    for(int j=1;j<=n;++j) if(!bit(tt,j))
    {
      int tt2=on(tt,j);
      int c=(tt==0 ? 0 : t + abs(a[i]-a[j]));
      f[tt2][j][c]=(f[tt2][j][c] + f[tt][i][t])%M;
    }
  for(int i=1;i<=n;++i) for(int t=0;t<=l;++t) kq=(kq+f[(1<<n)-1][i][t])%M;
  cout<<kq;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 72 ms 46044 KB Output is correct
2 Correct 276 ms 194388 KB Output is correct
3 Correct 344 ms 193784 KB Output is correct
4 Correct 256 ms 194680 KB Output is correct
5 Correct 267 ms 194680 KB Output is correct
6 Correct 360 ms 194552 KB Output is correct
7 Correct 237 ms 193784 KB Output is correct
8 Correct 319 ms 193784 KB Output is correct
9 Correct 369 ms 193784 KB Output is correct
10 Correct 256 ms 194520 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 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Correct 2 ms 376 KB Output is correct
11 Correct 72 ms 46044 KB Output is correct
12 Correct 276 ms 194388 KB Output is correct
13 Correct 344 ms 193784 KB Output is correct
14 Correct 256 ms 194680 KB Output is correct
15 Correct 267 ms 194680 KB Output is correct
16 Correct 360 ms 194552 KB Output is correct
17 Correct 237 ms 193784 KB Output is correct
18 Correct 319 ms 193784 KB Output is correct
19 Correct 369 ms 193784 KB Output is correct
20 Correct 256 ms 194520 KB Output is correct
21 Runtime error 11 ms 760 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -