oj.uz

Submission #821166

# Submission time Handle Problem Language Result Execution time Memory
821166 2023-08-11T07:53:07 Z Sandarach151 Magneti (COCI21_magneti) C++17
0 / 110
 6 ms 8148 KB 
#include<bits/stdc++.h>
using namespace std;

const long long MODD = 1000000007;

long long gett(vector<vector<long long>>& temp, long long i, long long j){
    if(i<0 || j<0){
        return 0LL;
    }
    else{
        return temp[i][j];
    }
}




int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    long long n, l;
    cin >> n >> l;
    long long arr[n];
    for(long long i=0; i<n; i++){
        cin >> arr[i];	
    }
    sort(arr, arr+n);
    vector<vector<long long>> ans(n, vector<long long>(l+1));
    vector<vector<long long>> pref(n, vector<long long>(l+1));    
    for(long long i=0; i<=l; i++){
        ans[0][i]=i;
        pref[0][i]=(gett(pref, 0, i-1)%MODD+ans[0][i]%MODD)%MODD;
    }
    for(long long i=1; i<n; i++){
        for(long long j=0; j<=l; j++){
			ans[i][j]+=2*(gett(pref, i-1, j-arr[i])-gett(pref, i-1, j-2*arr[i]+1));
			ans[i][j]%=MODD;
            ans[i][j]+=max(0LL, j-2*arr[i]+2)*gett(ans, i-1, j-2*arr[i]+1);
            ans[i][j]%=MODD;
            pref[i][j]=gett(pref, i, j-1)+ans[i][j];
            pref[i][j]%=MODD;
        }
    }
    cout << ans[n-1][l] << '\n';
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8148 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Incorrect 1 ms 1748 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

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

Subtask #3
0 / 30.0

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

Subtask #4
0 / 50.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8148 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Incorrect 1 ms 1748 KB Output isn't correct
4 Halted 0 ms 0 KB -