Contest Duration: ~ (local time) (100 minutes) Back to Home

Submission #2692152

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; ll X[1010], Y[1010], Z[1010];
ll dp[1010][1010];
//---------------------------------------------------------------------------------------------------
void _main() {
cin >> N >> M;
rep(i, 0, N) cin >> X[i] >> Y[i] >> Z[i];

ll ans = -infl;
rep(a, -1, 2) rep(b, -1, 2) rep(c, -1, 2) if (a) if (b) if (c) {
rep(i, 0, N + 1) rep(j, 0, M + 1) dp[i][j] = -infl;
dp[0][0] = 0;
rep(i, 0, N) rep(j, 0, M + 1) {
ll d = a * X[i] + b * Y[i] + c * Z[i];
chmax(dp[i + 1][j], dp[i][j]);
chmax(dp[i + 1][j + 1], dp[i][j] + d);
}
chmax(ans, dp[N][M]);
}
cout << ans << endl;
}

Submission Info

Submission Time 2018-06-17 10:59:37+0900 D - Patisserie ABC hamayanhamayan C++14 (GCC 5.4.1) 400 1943 Byte AC 23 ms 8192 KB

Test Cases

Set Name Score / Max Score Test Cases
Sample 0 / 0 sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
All 400 / 400 in01.txt, in02.txt, in03.txt, in04.txt, in05.txt, in06.txt, in07.txt, in08.txt, in09.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, sample_01.txt, sample_02.txt, sample_03.txt, sample_04.txt
Case Name Status Exec Time Memory
in01.txt 3 ms 6272 KB
in02.txt 3 ms 6272 KB
in03.txt 9 ms 7296 KB
in04.txt 14 ms 8192 KB
in05.txt 18 ms 8192 KB
in06.txt 23 ms 8192 KB
in07.txt 23 ms 8192 KB
in08.txt 12 ms 7936 KB
in09.txt 15 ms 8192 KB
in10.txt 8 ms 7296 KB
in11.txt 22 ms 8192 KB
in12.txt 22 ms 8192 KB
in13.txt 15 ms 7296 KB
in14.txt 9 ms 6784 KB
in15.txt 11 ms 7296 KB
in16.txt 14 ms 7424 KB
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