oj.uz

Submission #1013998

# Submission time Handle Problem Language Result Execution time Memory
1013998 2024-07-04T09:25:44 Z User0069 Skyscraper (JOI16_skyscraper) C++17
100 / 100
 131 ms 5200 KB 
#include<bits/stdc++.h>
#define taskname ""
#define el '\n'
#define fi first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
#define int ll
using namespace std;
using ll=long long;
using ull=unsigned long long;
using ld=long double;
#define Faster ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
using namespace std;
const int maxn=1e5+3;
const int mod=1e9+7;
const int INF=1e9+1;
int n,l,a[maxn],dp[2][103][1003][3];
signed main()
{
    if (fopen(taskname".INP","r"))
    {
        freopen(taskname".INP","r",stdin);
        freopen(taskname".OUT","w",stdout);
    }
    Faster
    cin>>n>>l;
    dp[1][1][0][0]=1;
    dp[1][1][0][2]=1;
    dp[1][1][0][1]=2;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    sort(a+1,a+n+1);
    for(int i=2;i<=n;i++)
    {
        int d=a[i]-a[i-1];
        for(int j=1;j<=i;j++)
        {
            for(int k=0;k<=l;k++)
            {
                for(int msk=0;msk<3;msk++)
                {
                    dp[i&1][j][k][msk]=0;
                    if(k>=(2*j-msk)*d)
                    {
                        (dp[i&1][j][k][msk]+=dp[1-(i&1)][j][k-(2*j-msk)*d][msk]*(2*j-msk))%=mod;
                    }// expand the group
                    if(msk>0&&k>=(2*j-msk+1)*d)
                    {
                        (dp[i&1][j][k][msk]+=dp[1-(i&1)][j][k-(2*j-msk+1)*d][msk-1]*(3-msk))%=mod;
                    }// stick group to the leftmost/rightmost point
                    if(k>=(2*(j-1)-msk)*d)
                    {
                        (dp[i&1][j][k][msk]+=dp[1-(i&1)][j-1][k-(2*(j-1)-msk)*d][msk]*(j-msk))%=mod;
                    }// add a new group
                    if(msk>0&&k>=(2*(j-1)-msk+1)*d)
                    {
                        (dp[i&1][j][k][msk]+=dp[1-(i&1)][j-1][k-(2*(j-1)-msk+1)*d][msk-1]*(3-msk))%=mod;
                    }// add a new group stick to the leftmost/rightmost point
                    if(k>=(2*(j+1)-msk)*d)
                    {
                        (dp[i&1][j][k][msk]+=dp[1-(i&1)][j+1][k-(2*(j+1)-msk)*d][msk]*j)%=mod;
                    }//connect 2 groups
//                    if(dp[i&1][j][k][msk]!=0) cout<<i<<" "<<j<<" "<<k<<" "<<msk<<":"<<dp[i&1][j][k][msk]<<"\n";
                }
            }
        }
    }
    int ans=0;
    for(int i=0;i<=l;i++)
    {
        (ans+=dp[n&1][1][i][2])%=mod;
    }
    cout<<ans;
}

Compilation message

skyscraper.cpp: In function 'int main()':
skyscraper.cpp:23:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   23 |         freopen(taskname".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
skyscraper.cpp:24:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   24 |         freopen(taskname".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
80.0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 1 ms 592 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 464 KB Output is correct
12 Correct 1 ms 604 KB Output is correct
13 Correct 1 ms 604 KB Output is correct
14 Correct 1 ms 604 KB Output is correct
15 Correct 1 ms 604 KB Output is correct
16 Correct 1 ms 604 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 604 KB Output is correct
19 Correct 1 ms 604 KB Output is correct
20 Correct 1 ms 604 KB Output is correct
21 Correct 1 ms 860 KB Output is correct
22 Correct 96 ms 3828 KB Output is correct
23 Correct 128 ms 4944 KB Output is correct
24 Correct 110 ms 4692 KB Output is correct
25 Correct 131 ms 4888 KB Output is correct
26 Correct 115 ms 5020 KB Output is correct
27 Correct 40 ms 2132 KB Output is correct
28 Correct 52 ms 2640 KB Output is correct
29 Correct 93 ms 3872 KB Output is correct
30 Correct 130 ms 5200 KB Output is correct