oj.uz

Submission #741118

# Submission time Handle Problem Language Result Execution time Memory
741118 2023-05-13T14:46:59 Z Mihailo Skyscraper (JOI16_skyscraper) C++17
0 / 100
 2 ms 1876 KB 
#include <bits/stdc++.h>
#define MOD 1000000007
using namespace std;

long long N, L, a[200], dp[150][150][1200][5], x;

int main() {
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin>>N>>L;
    for(int i=1; i<=N; i++) cin>>a[i];
    sort(a+1, a+N+1);
    dp[0][0][0][0]=1;
    for(int i=1; i<=N; i++) {
        for(int j=1; j<=N; j++) {
            for(int s=0; s<=L; s++) {
                x=2*j*(a[i+1]-a[i]);
                if(s-x>=0) {
                    dp[i][j][s][0]+=j*dp[i-1][j-1][s-x][0]+2*j*dp[i-1][j][s-x][0]+j*dp[i-1][j+1][s-x][0];
                }
                x=(2*j-1)*(a[i+1]-a[i]);
                if(s-x>=0) {
                    dp[i][j][s][1]+=(j-1)*dp[i-1][j-1][s-x][1]+(2*j-1)*dp[i-1][j][s-x][1]+j*dp[i-1][j+1][s-x][1];
                    dp[i][j][s][1]+=2*dp[i-1][j-1][s-x][0]+2*dp[i-1][j][s-x][0];
                }
                x=(2*j-2)*(a[i+1]-a[i]);
                if(s-x>=0) {
                    dp[i][j][s][2]+=max(0, (j-2))*dp[i-1][j-1][s-x][2]+(2*j-2)*dp[i-1][j][s-x][2]+j*dp[i-1][j+1][s-x][2];
                    dp[i][j][s][2]+=dp[i-1][j-1][s-x][1]+dp[i-1][j][s-x][1];
                }
                for(int k=0; k<=2; k++) dp[i][j][s][k]%=MOD;
            }
        }
    }
    long long rez=0;
    for(int i=0; i<=L; i++) rez+=dp[N][1][i][2];
    cout<<rez;
    return 0;
}

Subtask #1
0 / 5.0

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

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1236 KB Output is correct
2 Correct 1 ms 1868 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 2 ms 1876 KB Output is correct
5 Correct 2 ms 1876 KB Output is correct
6 Correct 2 ms 1872 KB Output is correct
7 Correct 1 ms 1364 KB Output is correct
8 Correct 1 ms 1492 KB Output is correct
9 Incorrect 2 ms 1748 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 80.0

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