oj.uz

Submission #1116757

# Submission time Handle Problem Language Result Execution time Memory
1116757 2024-11-22T10:41:50 Z Tai_xiu Skyscraper (JOI16_skyscraper) C++17
15 / 100
 2 ms 2552 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define i128 int128
#define ii pair<int,int>
#define ld long double
#define vi vector<int>
#define vvi vector<vi>
#define vii vector<pair<int,int>>
#define FOR(i,a,b) for (int i=a;i<=b;i++)
#define FOR1(i,a,b,c) for (int i=a;i<=b;i+=c)
#define REP(i,a,b) for (int i=a;i>=b;i--)
#define REP1(i,a,b,c) for(int i=b;i>=a;i-=c)
#define endh '\n';
#define len(a) a.length()
#define pb(c) push_back(c)
#define elif else if
#define ppb() pop_back()
#define rong std::npos
#define all(c) (c.begin(),c.end())
#define Z int
#define R double
#define lcm(a,b) ((int) (a/__gcd(a,b))*b)
#define mk(a,b) make_pair(a,b)
Z dx4[]={-1,1,0,0};
Z dy4[]={0,0,1,-1};
string co="YES",khong="NO";
const int mod=1e9+7;
Z dp[2][103][1003][4];
Z a[103];
Z n,L;
Z add (Z a,Z b)
{
    a%=mod;
    b%=mod;
    a+=b;
    return a%mod;
}
/*
30 1000
1 2 3 4 5 6 7 8 9 10
11 12 13 14 15 16 17 18 19 20
21 22 23 24 25 26 27 28 29 30
*/
signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    dp[1][1][0][0]=1;
    dp[1][1][0][1]=2;
    cin>>n>>L;
    FOR(i,1,n) cin>>a[i];
    sort(a+1,a+n+1);
    FOR(i,2,n){
        Z curr=(i&1);
        Z prev=(curr^1);
        FOR(cc,1,n){
            FOR(sum,0,L){
                FOR(bien,0,2){
                    Z val=dp[prev][cc][sum][bien];
                    Z newsum=(2*cc-bien)*(a[i]-a[i-1])+sum;
                    if (val==0) continue;
                    if (newsum<=L) {
                        // them 1 tplt
                        {


                        dp[curr][cc+1][newsum][bien]= add(dp[curr][cc+1][newsum][bien],(cc+1-bien)*val);
                        dp[curr][cc+1][newsum][bien+1]=add(dp[curr][cc+1][newsum][bien+1],(2-bien)*val);
                        }
                        // them vao 1 tplt
                        {

                        dp[curr][cc][newsum][bien]=add(dp[curr][cc][newsum][bien],(2*cc-bien)*val);
                        dp[curr][cc][newsum][bien+1]=add(dp[curr][cc][newsum][bien+1],(2-bien)*val);
                        }
                        // gop
                        {

                        dp[curr][cc-1][newsum][bien]=add(dp[curr][cc-1][newsum][bien],(cc-1)*val);
                        }
                    }
                    dp[prev][cc][sum][bien]=0;
                }
            }
        }

    }
    Z ans=0;
    FOR(i,0,L) ans=(ans+dp[n&1][1][i][2])%mod;
    cout<<ans;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

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

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 2384 KB Output isn't correct
2 Halted 0 ms 0 KB -