oj.uz

Submission #332640

# Submission time Handle Problem Language Result Execution time Memory
332640 2020-12-03T02:00:17 Z daniel920712 Skyscraper (JOI16_skyscraper) C++14
20 / 100
 1345 ms 250820 KB 
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
bool have[16390][20][105]={0};
long long DP[16390][20][105]={0};
long long MOD=1e9+7;
long long all[20];
long long tt[20];
long long N,M;
long long F(long long x,long long y,long long z)
{
    long long i;
    //printf("%lld %lld\n",N,M);
    if(z>M) return 0;
    if(x==0) return 1;
    if(have[x][y][z]) return DP[x][y][z];
    have[x][y][z]=1;
    for(i=0;i<N;i++)
    {
        if(x&(1<<i))
        {
            DP[x][y][z]+=F(x-(1<<i),i,z+(long long) abs(all[i]-all[y]));
            DP[x][y][z]%=MOD;
        }
    }
    return DP[x][y][z];
}
int main()
{
    long long i,ans=0,x;
    scanf("%lld %lld",&N,&M);

    for(i=0;i<N;i++)
    {
        tt[i]=i;
        scanf("%lld",&all[i]);
    }
    if(N<=8)
    {
        x=0;
        do
        {
            x=0;
            for(i=1;i<N;i++) x+=abs(all[tt[i]]-all[tt[i-1]]);
            //printf("%lld\n",x);
            ans+=(x<=M);
        }while(next_permutation(tt,tt+N));
    }
    else
    {
        for(i=0;i<N;i++)
        {
            ans+=F(((1<<N)-1)-(1<<i),i,0);
            ans%=MOD;
        }
    }
    printf("%lld\n",ans);

    return 0;
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:36:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   36 |     scanf("%lld %lld",&N,&M);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
skyscraper.cpp:41:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   41 |         scanf("%lld",&all[i]);
      |         ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 55660 KB Output is correct
2 Correct 247 ms 215916 KB Output is correct
3 Correct 938 ms 248840 KB Output is correct
4 Correct 208 ms 205556 KB Output is correct
5 Correct 178 ms 181280 KB Output is correct
6 Correct 903 ms 250500 KB Output is correct
7 Correct 191 ms 197116 KB Output is correct
8 Correct 871 ms 248844 KB Output is correct
9 Correct 1345 ms 250820 KB Output is correct
10 Correct 216 ms 210284 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 140 ms 55660 KB Output is correct
12 Correct 247 ms 215916 KB Output is correct
13 Correct 938 ms 248840 KB Output is correct
14 Correct 208 ms 205556 KB Output is correct
15 Correct 178 ms 181280 KB Output is correct
16 Correct 903 ms 250500 KB Output is correct
17 Correct 191 ms 197116 KB Output is correct
18 Correct 871 ms 248844 KB Output is correct
19 Correct 1345 ms 250820 KB Output is correct
20 Correct 216 ms 210284 KB Output is correct
21 Runtime error 32 ms 9196 KB Execution killed with signal 11 (could be triggered by violating memory limits)
22 Halted 0 ms 0 KB -