#474860 (C++14) No.1043 直列大学

• 問題: No.1043 直列大学
• ユーザー: ttkkggww
• 提出日時: 2020-05-01 22:58:33
• 言語: C++14 (gcc 12.3.0 + boost 1.83.0)
• 結果: WA (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 998 bytes
• コンパイル時間: 1,563 ms
• コンパイル使用メモリ: 170,632 KB
• 実行使用メモリ: 74,832 KB
• 最終ジャッジ日時: 2024-07-18 12:01:18
• 合計ジャッジ時間: 3,675 ms
• ジャッジサーバーID （参考情報）: judge4 / judge5

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	7 ms; 6,812 KB
testcase_01	AC	6 ms; 6,940 KB
testcase_02	AC	7 ms; 6,944 KB
testcase_03	AC	6 ms; 6,944 KB
testcase_04	AC	6 ms; 6,944 KB
testcase_05	AC	6 ms; 6,940 KB
testcase_06	AC	6 ms; 6,940 KB
testcase_07	AC	7 ms; 6,940 KB
testcase_08	AC	6 ms; 6,944 KB
testcase_09	AC	19 ms; 7,244 KB
testcase_10	AC	23 ms; 8,904 KB
testcase_11	AC	47 ms; 24,652 KB
testcase_12	AC	114 ms; 74,832 KB
testcase_13	AC	63 ms; 34,508 KB
testcase_14	AC	69 ms; 37,196 KB
testcase_15	AC	80 ms; 43,976 KB
testcase_16	AC	67 ms; 36,936 KB
testcase_17	AC	43 ms; 23,248 KB
testcase_18	AC	40 ms; 20,552 KB
testcase_19	AC	62 ms; 34,120 KB
testcase_20	AC	40 ms; 21,712 KB
testcase_21	AC	56 ms; 30,544 KB
testcase_22	AC	59 ms; 32,080 KB
testcase_23	AC	83 ms; 45,520 KB
testcase_24	AC	46 ms; 24,396 KB
testcase_25	AC	62 ms; 33,740 KB
testcase_26	AC	67 ms; 37,064 KB
testcase_27	AC	30 ms; 16,588 KB
testcase_28	AC	47 ms; 22,860 KB
testcase_29	WA	-
testcase_30	AC	54 ms; 31,948 KB

ソースコード

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll MOD = 1e9+7;
ll dpV[101][100001],dpR[101][100001];

int main()
{
	ll n,m;
	cin >> n >> m;
	vector<ll> V(n),R(m);
	for(ll i = 0;i<n;i++)cin >> V[i];
	for(ll i = 0;i<m;i++)cin >> R[i];
	ll A,B;
	cin >> A >> B;
	dpV[0][0]=dpR[0][0]=1;
	for(ll i = 0;i<n;i++)
	{
		for(ll j = 0;j<100001;j++)
		{
			if(dpV[i][j])
			{
				(dpV[i+1][j]+=dpV[i][j])%=MOD;
				(dpV[i+1][j+V[i]]+=dpV[i][j])%=MOD;
			}
		}
	}
	for(ll i =0;i<m;i++)
	{
		for(ll j = 0;j<100001;j++)
		{
			if(dpR[i][j])
			{
				(dpR[i+1][j]+=dpR[i][j])%=MOD;
				(dpR[i+1][j+R[i]]+=dpR[i][j])%=MOD;
			}
		}
	}
	ll ans = 0;
	dpR[m][0] = 0;
	vector<ll> sum(100002);
	for(ll i = 0;i<100001;i++)
	{
		(sum[i+1] += sum[i]+dpR[m][i])%=MOD;
		//cout<<sum[i+1]<<endl;
	}
	
	for(ll i = 1;i<100001;i++)
	{
		ll r,l;
		l = (i+B-1)/B;
		r = (i)/A;
		//cout<<i<<';'<<r<<' '<<l<<endl;
	(ans += ((sum[r+1]-sum[l])*dpV[n][i])%MOD)%=MOD;
		//cout<<ans<<endl;
	}
	cout<<ans<<endl;

}