Submission #5195581


Source Code Expand

Copy
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<b;i++)
#define rrep(i,a,b) for(int i=a;i>=b;i--)
#define fore(i,a) for(auto &i:a)
#define all(x) (x).begin(),(x).end()
//#pragma GCC optimize ("-O3")
using namespace std; void _main(); int main() { cin.tie(0); ios::sync_with_stdio(false); _main(); }
typedef long long ll; const int inf = INT_MAX / 2; const ll infl = 1LL << 60;
template<class T>bool chmax(T& a, const T& b) { if (a < b) { a = b; return 1; } return 0; }
template<class T>bool chmin(T& a, const T& b) { if (b < a) { a = b; return 1; } return 0; }
//---------------------------------------------------------------------------------------------------
/*---------------------------------------------------------------------------------------------------
            ∧_∧
      ∧_∧  (´<_` )  Welcome to My Coding Space!
     ( ´_ゝ`) /  ⌒i
    /   \     | |
    /   / ̄ ̄ ̄ ̄/  |
  __(__ニつ/     _/ .| .|____
     \/____/ (u ⊃
---------------------------------------------------------------------------------------------------*/






int N, M, K, A[1010];
ll dp[370][370];
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> M >> K;
	rep(i, 1, N + 1) cin >> A[i];

	rep(i, 0, N + 1) rep(m, 0, M + 1) dp[i][m] = -infl;
	dp[0][0] = 0;

	rep(i, 1, N + 1) rep(m, 1, M + 1) {
		rep(j, 0, i) if (i - j <= K) {
			chmax(dp[i][m], dp[j][m - 1] + A[i]);
		}
	}

	ll ans = -infl;
	rep(i, N - K + 1, N + 1) chmax(ans, dp[i][M]);

	if (ans < 0) ans = -1;

	cout << ans << endl;
}

Submission Info

Submission Time
Task G - 友達以上恋人以下
User hamayanhamayan
Language C++14 (GCC 5.4.1)
Score 400
Code Size 1775 Byte
Status
Exec Time 36 ms
Memory 1280 KB

Judge Result

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
Subtask1 400 / 400 sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt, subtask_1_00.txt, subtask_1_06.txt, subtask_1_07.txt, subtask_1_08.txt, subtask_1_09.txt, subtask_1_10.txt, subtask_1_16.txt, subtask_1_17.txt, subtask_1_18.txt, subtask_1_19.txt, subtask_1_20.txt, subtask_1_26.txt, subtask_1_27.txt, subtask_1_28.txt, subtask_1_29.txt, subtask_1_30.txt, subtask_1_36.txt, subtask_1_37.txt, subtask_1_38.txt, subtask_1_39.txt, subtask_1_40.txt, subtask_1_46.txt, subtask_1_47.txt, subtask_1_48.txt, subtask_1_49.txt, subtask_1_50.txt, subtask_1_56.txt, subtask_1_57.txt, subtask_1_58.txt, subtask_1_59.txt, subtask_1_60.txt, subtask_1_61.txt, subtask_1_62.txt, subtask_1_63.txt, subtask_1_64.txt, subtask_1_65.txt, subtask_1_66.txt, subtask_1_67.txt, subtask_1_68.txt, subtask_1_69.txt, subtask_1_70.txt, subtask_1_71.txt, subtask_1_72.txt, subtask_1_73.txt, subtask_1_74.txt, subtask_1_75.txt
Case Name Status Exec Time Memory
sample_01.txt 1 ms 256 KB
sample_02.txt 1 ms 256 KB
sample_03.txt 1 ms 256 KB
sample_04.txt 1 ms 256 KB
subtask_1_00.txt 30 ms 1280 KB
subtask_1_06.txt 1 ms 256 KB
subtask_1_07.txt 1 ms 256 KB
subtask_1_08.txt 1 ms 256 KB
subtask_1_09.txt 1 ms 256 KB
subtask_1_10.txt 1 ms 256 KB
subtask_1_16.txt 1 ms 256 KB
subtask_1_17.txt 1 ms 256 KB
subtask_1_18.txt 1 ms 256 KB
subtask_1_19.txt 1 ms 256 KB
subtask_1_20.txt 1 ms 256 KB
subtask_1_26.txt 1 ms 256 KB
subtask_1_27.txt 1 ms 256 KB
subtask_1_28.txt 1 ms 256 KB
subtask_1_29.txt 1 ms 256 KB
subtask_1_30.txt 1 ms 256 KB
subtask_1_36.txt 1 ms 256 KB
subtask_1_37.txt 1 ms 256 KB
subtask_1_38.txt 1 ms 256 KB
subtask_1_39.txt 1 ms 256 KB
subtask_1_40.txt 1 ms 256 KB
subtask_1_46.txt 2 ms 512 KB
subtask_1_47.txt 1 ms 512 KB
subtask_1_48.txt 2 ms 512 KB
subtask_1_49.txt 1 ms 512 KB
subtask_1_50.txt 2 ms 512 KB
subtask_1_56.txt 1 ms 512 KB
subtask_1_57.txt 2 ms 512 KB
subtask_1_58.txt 2 ms 512 KB
subtask_1_59.txt 2 ms 512 KB
subtask_1_60.txt 2 ms 512 KB
subtask_1_61.txt 23 ms 1280 KB
subtask_1_62.txt 15 ms 1280 KB
subtask_1_63.txt 12 ms 1280 KB
subtask_1_64.txt 29 ms 1280 KB
subtask_1_65.txt 36 ms 1280 KB
subtask_1_66.txt 27 ms 1280 KB
subtask_1_67.txt 24 ms 1280 KB
subtask_1_68.txt 8 ms 1280 KB
subtask_1_69.txt 25 ms 1280 KB
subtask_1_70.txt 18 ms 1280 KB
subtask_1_71.txt 16 ms 1280 KB
subtask_1_72.txt 20 ms 1280 KB
subtask_1_73.txt 24 ms 1280 KB
subtask_1_74.txt 6 ms 1280 KB
subtask_1_75.txt 33 ms 1280 KB