oj.uz

Submission #447553

# Submission time Handle Problem Language Result Execution time Memory
447553 2021-07-26T18:12:26 Z nguot Skyscraper (JOI16_skyscraper) C++14
100 / 100
 115 ms 50992 KB 
#include <bits/stdc++.h>
using namespace std;
#define int long long
#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 fori(x,a,b) for(int x=a;x<=b;x++)
#define ford(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<int,int>
#define mt make_tuple
#define all(a) a.begin(),a.end()
#define reset(f,x) memset(f,x,sizeof(f))
#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);

const int mod = 1e9+7;
int f[105][105][1005][3];
int n,l,a[105];

void add(int &a,int b)
{
    a+=b;
    if(a>=mod) a-=mod;
}
main()
{
    //freopen("task.inp","r",stdin);
    fasty;
    cin>>n>>l;
    fori(i,1,n) cin>>a[i];
    sort(a+1,a+n+1);
    if(n==1) return cout<<1,0;
    f[0][0][0][0] = 1;
    //ed : so luong end point da dc fill
    a[n+1] = 100000;
    fori(i,1,n) fori(j,1,i) fori(k,0,l) fori(ed,0,2)
    {
        int diff = (2*j-ed)*(a[i+1]-a[i]);//neu a[i] ko phai ed(end point)=> xuat hien 2 lan hoac ko xuat hien
        if(k<diff || i+j+1-ed>n) continue;

        add(f[i][j][k][ed],f[i-1][j-1][k-diff][ed]);//a[i] ko la endpoint
        if(ed>=1) add(f[i][j][k][ed],(3-ed)*f[i-1][j-1][k-diff][ed-1]%mod);//a[i] la 1 endpoint;

        add(f[i][j][k][ed],(2*j-ed)*f[i-1][j][k-diff][ed]%mod);//a[i] nhet vao 1 cc ko chua endpoint;

        if(ed==1) add(f[i][j][k][ed],2*j*f[i-1][j][k-diff][ed-1]%mod);//chon 1 dau lam endpoint dau tien
        if(ed==2)
        {
           if(i==n) add(f[i][j][k][ed],f[i-1][j][k-diff][ed-1]);//1 cach duy nhat la a[n]
           else if(j>1) add(f[i][j][k][ed],(j-1)*f[i-1][j][k-diff][ed-1]%mod);
        }

        if(ed==2)
        {
            if(i==n) add(f[i][j][k][ed],f[i-1][j+1][k-diff][ed]);//hop 2 cc con lai
            else add(f[i][j][k][ed],j*(j-1)%mod*f[i-1][j+1][k-diff][ed]%mod);
        }
        else if(ed==1) add(f[i][j][k][ed],j*j%mod*f[i-1][j+1][k-diff][ed]%mod);
        else add(f[i][j][k][ed],j*(j+1)%mod*f[i-1][j+1][k-diff][ed]%mod);
    }

    int kq = 0;
    fori(k,0,l) add(kq,f[n][1][k][2]);
    cout<<kq;
}

Compilation message

skyscraper.cpp:32:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   32 | 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 332 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 1 ms 448 KB Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 0 ms 328 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 716 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 1 ms 460 KB Output is correct
8 Correct 1 ms 460 KB Output is correct
9 Correct 1 ms 716 KB Output is correct
10 Correct 1 ms 448 KB Output is correct
11 Correct 1 ms 588 KB Output is correct
12 Correct 1 ms 588 KB Output is correct
13 Correct 1 ms 588 KB Output is correct
14 Correct 1 ms 580 KB Output is correct
15 Correct 1 ms 588 KB Output is correct
16 Correct 1 ms 716 KB Output is correct
17 Correct 1 ms 588 KB Output is correct
18 Correct 1 ms 588 KB Output is correct
19 Correct 1 ms 588 KB Output is correct
20 Correct 1 ms 588 KB Output is correct
21 Correct 2 ms 2380 KB Output is correct
22 Correct 99 ms 35736 KB Output is correct
23 Correct 106 ms 47368 KB Output is correct
24 Correct 97 ms 46788 KB Output is correct
25 Correct 115 ms 50760 KB Output is correct
26 Correct 99 ms 46196 KB Output is correct
27 Correct 39 ms 23488 KB Output is correct
28 Correct 50 ms 26948 KB Output is correct
29 Correct 87 ms 41304 KB Output is correct
30 Correct 111 ms 50992 KB Output is correct