oj.uz

Submission #706299

# Submission time Handle Problem Language Result Execution time Memory
706299 2023-03-06T09:09:08 Z ByeWorld Skyscraper (JOI16_skyscraper) C++14
15 / 100
 7 ms 3404 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O1")
#define int long long
#define fi first
#define se second
#define pb push_back
#define lb lower_bound
#define ub upper_bound
using namespace std;
const int MAXN = 110;
const double SMALL = 1e-6;
const int INF = 5e5+10;
const int MX = 2e12;
const int MOD = 1e9+7;
typedef pair<int,int> pii;
typedef pair<pii,int> ipii;
int sum(int a, int b){
    return (a+b)%MOD;
}
int sub(int a, int b){
    return (a+MOD-b)%MOD;
}
int mul(int a, int b){
    return (a*b)%MOD;
}

int dp[110][110][1010][4]; // dp[id][cc][sum][co]
int a[110];

signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, L; cin >> n >> L;
    for(int i=1; i<=n; i++) cin >> a[i];
    sort(a+1, a+n+1);
    
    dp[1][1][0][0] = 1; dp[1][1][0][1] = 2; dp[1][1][0][2] = 1;
    
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            for(int k=0; k<=L; k++){
                for(int co=0; co<=2; co++){
                    int dif = a[i+1]-a[i]; int te = k + dif*(2*j-co); 
                    // O+O j-1
                    dp[i+1][j-1][te][co] = sum(mul(j-1, dp[i][j][k][co]), dp[i+1][j-1][te][co]);
                    
                    // O+ 2j-co
                    dp[i+1][j][te][co] = sum(mul(2*j-co, dp[i][j][k][co]), dp[i+1][j][te][co]);
                    
                    // O+| 2-co 
                    dp[i+1][j][te][co+1] = sum(mul(2-co, dp[i][j][k][co]), dp[i+1][j][te][co+1]);
                    
                    // + j+1-co
                    dp[i+1][j+1][te][co] = sum(mul(j+1-co, dp[i][j][k][co]), dp[i+1][j+1][te][co]);
                    
                    // +| 2-co
                    dp[i+1][j+1][te][co+1] = sum(mul(2-co, dp[i][j][k][co]), dp[i+1][j+1][te][co+1]);
                    
                    //if(dp[i][j][k][co] != 0){
                    //    cout << i << ' ' << j <<  ' '<< k << ' ' << co << ' '<< dp[i][j][k][co]<<'\n';
                    //}
                }
            }
        }
    }
    
    int ans = 0;
    for(int i=0; i<=L; i++) ans = sum(ans, dp[n][1][i][2]);
    cout << ans << '\n';
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Incorrect 7 ms 3404 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 1364 KB Output is correct
2 Correct 3 ms 2380 KB Output is correct
3 Correct 3 ms 1660 KB Output is correct
4 Correct 4 ms 2388 KB Output is correct
5 Correct 4 ms 2380 KB Output is correct
6 Correct 3 ms 2120 KB Output is correct
7 Correct 2 ms 1620 KB Output is correct
8 Correct 2 ms 1608 KB Output is correct
9 Correct 2 ms 1748 KB Output is correct
10 Correct 3 ms 2260 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 328 KB Output is correct
4 Correct 2 ms 724 KB Output is correct
5 Incorrect 7 ms 3404 KB Output isn't correct
6 Halted 0 ms 0 KB -