Submission #821166

#	Time	Username	Problem	Language	Result	Execution time	Memory
821166		Sandarach151	Magneti (COCI21_magneti)	C++17	0 / 110	6 ms	8148 KiB

Main

#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
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 50