oj.uz

Submission #528545

# Submission time Handle Problem Language Result Execution time Memory
528545 2022-02-20T13:45:02 Z aSSSd Skyscraper (JOI16_skyscraper) C++14
20 / 100
 268 ms 194828 KB 
//#pragma GCC optimize("O2,unroll-loops")
//#pragma GCC target("avx,avx2")
#include <bits/stdc++.h>
using namespace std;
#define in ({int x=0;int c=getchar(),n=0;for(;!isdigit(c);c=getchar()) n=(c=='-');for(;isdigit(c);c=getchar()) x=x*10+c-'0';n?-x:x;})
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rnd(int l,int r)
{
    return l+rng()%(r-l+1);
}
#define fasty ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define forinc(x,a,b) for(int x=a;x<=b;x++)
#define fordec(x,a,b) for(int x=a;x>=b;x--)
#define forv(a,b) for(auto&a:b)
#define fi first
#define se second
#define pb push_back
#define ii pair<long long,long long>
#define getbit(x,i) ((x>>(i))&1)
#define batbit(x,i) (x|(1ll<<(i)))
#define tatbit(x,i) (x&~(1<<(i)))
#define gg exit(0);
#define all(a) a.begin() , a.end()
const int N = 14;
const int mod = 1e9 + 7;
int n, L;
int a[20];
int f[1<<15][15][210];

main()
{
    fasty;
    cin >> n >> L;
    forinc(i,1,n) cin >> a[i];
    if(n <= 10)
    {
        int cnt=0;
        sort(a+1, a+n+1);
        do
        {
            int sum=0;
            forinc(i,1,n-1) sum += abs(a[i] - a[i+1]);
            if(sum <=  L) cnt++;
        }
        while(next_permutation(a+1, a+n + 1));
        cout << cnt;
        return 0;
    }
    f[0][0][0] = 1;
    for(int tt =0 ; tt < (1<<n) - 1 ; tt++) forinc(i, 0, n) forinc(l, 0, L) if(f[tt][i][l])
    {
        for(int j=1; j<=n; ++j) if(!getbit(tt,j-1))
        {
            int tt2=batbit(tt,j-1);
            int c=(tt==0 ? 0 : l + abs(a[i]-a[j]));
            f[tt2][j][c]=(f[tt2][j][c] + f[tt][i][l])%mod;
        }
    }
    int res=0;
    for(int i=1;i<=n;++i) for(int t=0;t<=L;++t) res=(res+f[(1<<n)-1][i][t])%mod;
    cout << res;


}

Compilation message

skyscraper.cpp:30:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   30 | main()
      | ^~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 46040 KB Output is correct
2 Correct 137 ms 194752 KB Output is correct
3 Correct 222 ms 193980 KB Output is correct
4 Correct 168 ms 194756 KB Output is correct
5 Correct 133 ms 194828 KB Output is correct
6 Correct 239 ms 194500 KB Output is correct
7 Correct 133 ms 193408 KB Output is correct
8 Correct 212 ms 194004 KB Output is correct
9 Correct 268 ms 194116 KB Output is correct
10 Correct 145 ms 194492 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 284 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 2 ms 204 KB Output is correct
11 Correct 44 ms 46040 KB Output is correct
12 Correct 137 ms 194752 KB Output is correct
13 Correct 222 ms 193980 KB Output is correct
14 Correct 168 ms 194756 KB Output is correct
15 Correct 133 ms 194828 KB Output is correct
16 Correct 239 ms 194500 KB Output is correct
17 Correct 133 ms 193408 KB Output is correct
18 Correct 212 ms 194004 KB Output is correct
19 Correct 268 ms 194116 KB Output is correct
20 Correct 145 ms 194492 KB Output is correct
21 Runtime error 7 ms 544 KB Execution killed with signal 11
22 Halted 0 ms 0 KB -