oj.uz

Submission #488463

# Submission time Handle Problem Language Result Execution time Memory
488463 2021-11-19T07:26:56 Z Tenis0206 Skyscraper (JOI16_skyscraper) C++11
15 / 100
 3 ms 972 KB 
#include <bits/stdc++.h>

using namespace std;

const int Mod = 1e9 + 7;

int n,l;
int v[1005];

int dp[105][105][1005][2][2];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
  //  freopen("nr.in","r",stdin);
  //  freopen("nr.out","w",stdout);
    cin>>n>>l;
    for(int i=1; i<=n; i++)
    {
        cin>>v[i];
    }
    sort(v+1,v+n+1);
    v[n+1] = v[n];
    dp[1][0][0][0][0] = 1;
    dp[1][0][v[2]-v[1]][0][1] = 1;
    dp[1][0][v[2]-v[1]][1][0] = 1;
    dp[1][0][2*(v[2]-v[1])][1][1] = 1;
    for(int i=1; i<n; i++)
    {
        for(int j=0; j<i; j++)
        {
            for(int s=0; s<=l; s++)
            {
                ///adaugam un element in centru
                for(int a=0; a<=1; a++)
                {
                    for(int b=0; b<=1; b++)
                    {
                        ///taiem ambele spatii
                        if(j>0)
                        {
                            dp[i+1][j-1][s+(2*(j-1)+a+b)*(v[i+2]-v[i+1])][a][b]+=(1LL * dp[i][j][s][a][b] * j) % Mod;
                            dp[i+1][j-1][s+(2*(j-1)+a+b)*(v[i+2]-v[i+1])][a][b]%=Mod;
                        }
                        ///taiem un singur spatiu
                        dp[i+1][j][s+(2*j+a+b)*(v[i+2]-v[i+1])][a][b]+=(1LL * dp[i][j][s][a][b] * j * 2) % Mod;
                        dp[i+1][j][s+(2*j+a+b)*(v[i+2]-v[i+1])][a][b]%=Mod;
                        ///taiem ambele spatii
                        dp[i+1][j+1][s+(2*(j+1)+a+b)*(v[i+2]-v[i+1])][a][b]+=(1LL * dp[i][j][s][a][b] * j) % Mod;
                        dp[i+1][j+1][s+(2*(j+1)+a+b)*(v[i+2]-v[i+1])][a][b]%=Mod;
                    }
                }
                ///adaugam un element in fata
                for(int b=0;b<=1;b++)
                {
                    ///se creaza un nou spatiu

                    ///ramane loc de adaugat in fata
                    dp[i+1][j+1][s+(2*(j+1)+1+b)*(v[i+2]-v[i+1])][1][b]+=dp[i][j][s][1][b];
                    dp[i+1][j+1][s+(2*(j+1)+1+b)*(v[i+2]-v[i+1])][1][b]%=Mod;
                    ///nu ramane loc de adaugat in fata
                    dp[i+1][j+1][s+(2*(j+1)+0+b)*(v[i+2]-v[i+1])][0][b]+=dp[i][j][s][1][b];
                    dp[i+1][j+1][s+(2*(j+1)+0+b)*(v[i+2]-v[i+1])][0][b]%=Mod;

                    ///nu se creeaza un nou spatiu

                    ///ramane loc de adaugat in fata
                    dp[i+1][j][s+(2*j+1+b)*(v[i+2]-v[i+1])][1][b]+=dp[i][j][s][1][b];
                    dp[i+1][j][s+(2*j+1+b)*(v[i+2]-v[i+1])][1][b]%=Mod;
                    ///nu ramane loc de adaugat in fata
                    dp[i+1][j][s+(2*j+0+b)*(v[i+2]-v[i+1])][0][b]+=dp[i][j][s][1][b];
                    dp[i+1][j][s+(2*j+0+b)*(v[i+2]-v[i+1])][0][b]%=Mod;

                }

                ///adaugam un element in spate
                for(int a=0;a<=1;a++)
                {
                    ///se creeaza un nou spatiu

                    ///ramane loc de adaugat in spate
                    dp[i+1][j+1][s+(2*(j+1)+a+1)*(v[i+2]-v[i+1])][a][1]+=dp[i][j][s][a][1];
                    dp[i+1][j+1][s+(2*(j+1)+a+1)*(v[i+2]-v[i+1])][a][1]%=Mod;
                    ///nu ramane loc de adaugat in fata
                    dp[i+1][j+1][s+(2*(j+1)+a+0)*(v[i+2]-v[i+1])][a][0]+=dp[i][j][s][a][1];
                    dp[i+1][j+1][s+(2*(j+1)+a+0)*(v[i+2]-v[i+1])][a][0]%=Mod;

                    ///nu se creeaza un nou spatiu
                    dp[i+1][j][s+(2*j+a+1)*(v[i+2]-v[i+1])][a][1]+=dp[i][j][s][a][1];
                    dp[i+1][j][s+(2*j+a+1)*(v[i+2]-v[i+1])][a][1]%=Mod;
                    ///nu ramane loc de adaugat in fata
                    dp[i+1][j][s+(2*j+a+0)*(v[i+2]-v[i+1])][a][0]+=dp[i][j][s][a][1];
                    dp[i+1][j][s+(2*j+a+0)*(v[i+2]-v[i+1])][a][0]%=Mod;
                }
            }
        }
    }
    long long rez = 0;
    for(int i=0;i<=l;i++)
    {
        rez+=dp[n][0][i][0][0];
        rez%=Mod;
    }
    cout<<rez<<'\n';
    return 0;
}

Subtask #1
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 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Incorrect 3 ms 964 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 716 KB Output is correct
2 Correct 1 ms 844 KB Output is correct
3 Correct 1 ms 844 KB Output is correct
4 Correct 1 ms 844 KB Output is correct
5 Correct 1 ms 972 KB Output is correct
6 Correct 2 ms 972 KB Output is correct
7 Correct 1 ms 844 KB Output is correct
8 Correct 2 ms 844 KB Output is correct
9 Correct 1 ms 844 KB Output is correct
10 Correct 1 ms 844 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 332 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Incorrect 3 ms 964 KB Output isn't correct
6 Halted 0 ms 0 KB -