CODE FESTIVAL 2016 Tournament Round 3 (Parallel)

Submission #1721141

Source codeソースコード

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key
 
typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

ll a[100001];
int n,m,k;
ll dp[100001][301];

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin>>n>>m>>k;
	for(int i = 0; i < n; i++)
	{
		cin>>a[i];
	}
	for(int i = 0; i < n; i++)
	{
		dp[i][1] = a[i];
	}
	ll sum = a[0];
	for(int j = 2; j <= k; j++)
	{
		deque<ll> dq;
		dp[j-1][j] = sum+ll(j)*a[j-1];
		sum=dp[j-1][j];
		for(int z = 0; z < j; z++)
		{
			while(!dq.empty()&&dp[dq.back()][j-1]<=dp[z][j-1]) dq.pop_back();
			dq.push_back(z);
		}	
		for(int i = j; i < n; i++)
		{
			dp[i][j] = ll(j)*a[i] + dp[dq.front()][j-1];
			while(!dq.empty()&&dp[dq.back()][j-1]<=dp[i][j-1]) dq.pop_back();
			dq.push_back(i);
			while(!dq.empty()&&i-dq.front()>=m) dq.pop_front();
		}
	}
	ll ans = 0;
	for(int i = 0; i < n; i++) ans = max(ans, dp[i][k]);
	cout<<ans<<'\n';
}

Submission

Task問題 A - ストラックアウト / Struck Out
User nameユーザ名 vjudge2
Created time投稿日時
Language言語 C++14 (GCC 5.4.1)
Status状態 AC
Score得点 700
Source lengthソースコード長 1357 Byte
File nameファイル名
Exec time実行時間 639 ms
Memory usageメモリ使用量 236160 KB

Test case

Set

Set name Score得点 / Max score Cases
Sample - sample_1.txt,sample_2.txt,sample_3.txt
subtask1 100 / 100 sample_2.txt,subtask_1_1.txt,subtask_1_2.txt,subtask_1_3.txt,subtask_1_4.txt,subtask_1_5.txt,subtask_1_6.txt,subtask_1_7.txt,subtask_1_8.txt,subtask_1_9.txt
subtask2 200 / 200 sample_1.txt,sample_2.txt,sample_3.txt,subtask_2_1.txt,subtask_2_2.txt,subtask_2_3.txt,subtask_2_4.txt,subtask_2_5.txt,subtask_2_6.txt,subtask_2_7.txt,subtask_2_8.txt,subtask_2_9.txt
subtask3 300 / 300 sample_1.txt,sample_2.txt,sample_3.txt,subtask_2_1.txt,subtask_2_2.txt,subtask_2_3.txt,subtask_2_4.txt,subtask_2_5.txt,subtask_2_6.txt,subtask_2_7.txt,subtask_2_8.txt,subtask_2_9.txt,subtask_3_1.txt,subtask_3_2.txt,subtask_3_3.txt,subtask_3_4.txt,subtask_3_5.txt,subtask_3_6.txt,subtask_3_7.txt,subtask_3_8.txt,subtask_3_9.txt
All 100 / 100 sample_1.txt,sample_2.txt,sample_3.txt,sample_1.txt,sample_2.txt,sample_3.txt,subtask_1_1.txt,subtask_1_2.txt,subtask_1_3.txt,subtask_1_4.txt,subtask_1_5.txt,subtask_1_6.txt,subtask_1_7.txt,subtask_1_8.txt,subtask_1_9.txt,subtask_2_1.txt,subtask_2_2.txt,subtask_2_3.txt,subtask_2_4.txt,subtask_2_5.txt,subtask_2_6.txt,subtask_2_7.txt,subtask_2_8.txt,subtask_2_9.txt,subtask_3_1.txt,subtask_3_2.txt,subtask_3_3.txt,subtask_3_4.txt,subtask_3_5.txt,subtask_3_6.txt,subtask_3_7.txt,subtask_3_8.txt,subtask_3_9.txt,subtask_4_1.txt,subtask_4_10.txt,subtask_4_11.txt,subtask_4_12.txt,subtask_4_13.txt,subtask_4_2.txt,subtask_4_3.txt,subtask_4_4.txt,subtask_4_5.txt,subtask_4_6.txt,subtask_4_7.txt,subtask_4_8.txt,subtask_4_9.txt

Test case

Case name Status状態 Exec time実行時間 Memory usageメモリ使用量
sample_1.txt AC 1 ms 2304 KB
sample_2.txt AC 1 ms 2304 KB
sample_3.txt AC 2 ms 2304 KB
subtask_1_1.txt AC 2 ms 2560 KB
subtask_1_2.txt AC 59 ms 26880 KB
subtask_1_3.txt AC 639 ms 236160 KB
subtask_1_4.txt AC 7 ms 14592 KB
subtask_1_5.txt AC 66 ms 236160 KB
subtask_1_6.txt AC 2 ms 2816 KB
subtask_1_7.txt AC 238 ms 236160 KB
subtask_1_8.txt AC 602 ms 236160 KB
subtask_1_9.txt AC 3 ms 3456 KB
subtask_2_1.txt AC 2 ms 3072 KB
subtask_2_2.txt AC 2 ms 3072 KB
subtask_2_3.txt AC 2 ms 3072 KB
subtask_2_4.txt AC 2 ms 2816 KB
subtask_2_5.txt AC 2 ms 2432 KB
subtask_2_6.txt AC 1 ms 2432 KB
subtask_2_7.txt AC 2 ms 3072 KB
subtask_2_8.txt AC 2 ms 3072 KB
subtask_2_9.txt AC 2 ms 3072 KB
subtask_3_1.txt AC 112 ms 236160 KB
subtask_3_2.txt AC 112 ms 236160 KB
subtask_3_3.txt AC 110 ms 236160 KB
subtask_3_4.txt AC 90 ms 190976 KB
subtask_3_5.txt AC 7 ms 14592 KB
subtask_3_6.txt AC 86 ms 236160 KB
subtask_3_7.txt AC 114 ms 236160 KB
subtask_3_8.txt AC 13 ms 26880 KB
subtask_3_9.txt AC 114 ms 236160 KB
subtask_4_1.txt AC 602 ms 236160 KB
subtask_4_10.txt AC 552 ms 236160 KB
subtask_4_11.txt AC 639 ms 236160 KB
subtask_4_12.txt AC 637 ms 236160 KB
subtask_4_13.txt AC 632 ms 236160 KB
subtask_4_2.txt AC 628 ms 236160 KB
subtask_4_3.txt AC 604 ms 236160 KB
subtask_4_4.txt AC 602 ms 236160 KB
subtask_4_5.txt AC 518 ms 236160 KB
subtask_4_6.txt AC 99 ms 236160 KB
subtask_4_7.txt AC 356 ms 236160 KB
subtask_4_8.txt AC 593 ms 236160 KB
subtask_4_9.txt AC 300 ms 236160 KB