提出 #3204075


ソースコード 拡げる

Copy
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<map>
#include<utility>
#include<set>
#include<stack>
#include<list>
#include<deque>
#include<bitset>
#include<iomanip>
#include<cstring>
#include<sstream>
#include<cstdio>
#include<cstdlib>
#include<climits>
#include<cmath>
#include<cctype>


#define pb push_back
#define mp make_pair
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define ren(i,a,b) for(int i=a;i>=b;i--)
#define ff first
#define ss second
#define pll pair<long long int,long long int>
#define pii pair<int,int>
#define vll vector<long long int>
#define vii vector<int>
#define gi(n) scanf("%d",&n)
#define gll(n) scanf("%lld",&n)
#define gstr(n) scanf("%s",n)
#define gl(n) cin >> n
#define oi(n) printf("%d",n)
#define oll(n) printf("%lld",n)
#define ostr(n) printf("%s",n)
#define ol(n) cout << n
#define os cout<<" "
#define on cout<<"\n"
#define o2(a,b) cout<<a<<" "<<b
#define all(n) n.begin(),n.end()
#define present(s,x) (s.find(x) != s.end())
#define cpresent(s,x) (find(all(s),x) != s.end())
#define tr(container, it) for(__typeof(container.begin()) it = container.begin(); it != container.end(); it++)
using namespace std;

typedef unsigned long long int ull;
typedef long long int ll;
typedef long double ld;
typedef vector<vector<ll> > mat;

int lim=305;

ll n,x,a[300005],dp[300005],inf=1e18+7;

int main()
{ios_base::sync_with_stdio(false);

cin>>n>>x;

rep(i,1,n)cin>>a[i];

dp[0]=n*x;

rep(i,1,n)dp[i]=inf;

rep(i,0,n)
{
	int hi=min((int)n,i+lim);
	rep(j,i+1,hi)
	{
		ll cnt=1;
		ll s=a[j];
		ren(k,j,i+1)
		{
			s+=(cnt+1)*(cnt+1)*(a[k]-a[k-1]);
			cnt++;
		}
		dp[j]=min(dp[j],dp[i]+s+cnt*cnt*a[i]+x);
	}
	//o2(dp[1],dp[2]);on;
}
ol(dp[n]);
return 0;
}

提出情報

提出日時
問題 B - Garbage Collector
ユーザ abisheka
言語 C++14 (GCC 5.4.1)
得点 0
コード長 1804 Byte
結果
実行時間 2103 ms
メモリ 3840 KB

ジャッジ結果

セット名 得点 / 配点 テストケース
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
Subtask1 0 / 400 sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, stest_01.txt, stest_02.txt, stest_03.txt, stest_04.txt, stest_05.txt, stest_06.txt, stest_07.txt, stest_08.txt, stest_09.txt, stest_10.txt, stest_11.txt, stest_12.txt
All 0 / 300 sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, stest_01.txt, stest_02.txt, stest_03.txt, stest_04.txt, stest_05.txt, stest_06.txt, stest_07.txt, stest_08.txt, stest_09.txt, stest_10.txt, stest_11.txt, stest_12.txt, test_13.txt, test_14.txt, test_15.txt, test_16.txt, test_17.txt, test_18.txt, test_19.txt, test_20.txt, test_21.txt, test_22.txt, test_23.txt, test_24.txt, test_25.txt, test_26.txt, test_27.txt, test_28.txt
ケース名 結果 実行時間 メモリ
sample_01.txt 2 ms 2304 KB
sample_02.txt 1 ms 2304 KB
sample_03.txt 1 ms 2304 KB
sample_04.txt 1 ms 2304 KB
stest_01.txt 101 ms 2304 KB
stest_02.txt 101 ms 2304 KB
stest_03.txt 1 ms 2304 KB
stest_04.txt 2 ms 2304 KB
stest_05.txt 80 ms 2304 KB
stest_06.txt 59 ms 2304 KB
stest_07.txt 101 ms 2304 KB
stest_08.txt 101 ms 2304 KB
stest_09.txt 30 ms 2304 KB
stest_10.txt 101 ms 2304 KB
stest_11.txt 101 ms 2304 KB
stest_12.txt 7 ms 2304 KB
test_13.txt 2103 ms 3840 KB
test_14.txt 2103 ms 3840 KB
test_15.txt 2103 ms 2560 KB
test_16.txt 2103 ms 3840 KB
test_17.txt 2103 ms 3840 KB
test_18.txt 1652 ms 2560 KB
test_19.txt 2103 ms 3840 KB
test_20.txt 2103 ms 3840 KB
test_21.txt 2103 ms 3840 KB
test_22.txt 2103 ms 3840 KB
test_23.txt 2103 ms 3840 KB
test_24.txt 2103 ms 3840 KB
test_25.txt 2103 ms 3072 KB
test_26.txt 2103 ms 3840 KB
test_27.txt 2103 ms 3840 KB
test_28.txt 2103 ms 3584 KB