Submission #6701800

Source Code Expand

#include "bits/stdc++.h"
#define in std::cin
#define out std::cout
#define rep(i,N) for(LL i=0;i<N;++i)
typedef long long int LL;

const LL inf = 1123456789012345;
LL N, D;
std::vector<std::vector<LL>>M, memo;

LL dp(LL i, LL j)
{
	if (i == D) return 0;
	if (j == N + 1) return inf;
	if (memo[i][j] != -1) return memo[i][j];
	LL res1 = dp(i + 1, j) + std::abs(M[i][j] - (M[i][N] - M[i][j]));
	LL res2 = dp(i, j + 1);
	return memo[i][j] = std::min(res1, res2);
}

int main()
{
	in >> N >> D;
	M.resize(D, std::vector<LL>(N + 1));
	rep(i, D) rep(j, N) in >> M[i][j + 1];

	memo.resize(D, std::vector<LL>(N + 1, -1));
	rep(i, D) rep(j, N) M[i][j + 1] += M[i][j];
	out << dp(0, 0) << std::endl;
}

Submission Info

Submission Time
Task F - 天秤とコイン (Balance and Coins)
User Bwambocos
Language C++14 (GCC 5.4.1)
Score 100
Code Size 723 Byte
Status AC
Exec Time 1627 ms
Memory 63104 KiB

Judge Result

Set Name Sample 1 Sample 2 Sample 3 Subtask 1 Subtask 2 Subtask 3 Subtask 4 Subtask 5
Score / Max Score 0 / 0 0 / 0 0 / 0 8 / 8 8 / 8 14 / 14 24 / 24 46 / 46
Status
AC × 1
AC × 1
AC × 1
AC × 5
AC × 8
AC × 15
AC × 27
AC × 52
Set Name Test Cases
Sample 1 sample_01
Sample 2 sample_02
Sample 3 sample_03
Subtask 1 subtask1_01, subtask1_02, subtask1_03, subtask1_04, subtask1_05
Subtask 2 sample_01, subtask2_01, subtask2_02, subtask2_03, subtask2_04, subtask2_05, subtask2_06, subtask2_07
Subtask 3 sample_01, sample_02, sample_03, subtask3_01, subtask3_02, subtask3_03, subtask3_04, subtask3_05, subtask3_06, subtask3_07, subtask3_08, subtask3_09, subtask3_10, subtask3_11, subtask3_12
Subtask 4 sample_01, sample_02, sample_03, subtask3_01, subtask3_02, subtask3_03, subtask3_04, subtask3_05, subtask3_06, subtask3_07, subtask3_08, subtask3_09, subtask3_10, subtask3_11, subtask3_12, subtask4_01, subtask4_02, subtask4_03, subtask4_04, subtask4_05, subtask4_06, subtask4_07, subtask4_08, subtask4_09, subtask4_10, subtask4_11, subtask4_12
Subtask 5 sample_01, sample_02, sample_03, subtask1_01, subtask1_02, subtask1_03, subtask1_04, subtask1_05, subtask2_01, subtask2_02, subtask2_03, subtask2_04, subtask2_05, subtask2_06, subtask2_07, subtask3_01, subtask3_02, subtask3_03, subtask3_04, subtask3_05, subtask3_06, subtask3_07, subtask3_08, subtask3_09, subtask3_10, subtask3_11, subtask3_12, subtask4_01, subtask4_02, subtask4_03, subtask4_04, subtask4_05, subtask4_06, subtask4_07, subtask4_08, subtask4_09, subtask4_10, subtask4_11, subtask4_12, subtask5_01, subtask5_02, subtask5_03, subtask5_04, subtask5_05, subtask5_06, subtask5_07, subtask5_08, subtask5_09, subtask5_10, subtask5_11, subtask5_12, subtask5_13
Case Name Status Exec Time Memory
sample_01 AC 1 ms 256 KiB
sample_02 AC 1 ms 256 KiB
sample_03 AC 1 ms 256 KiB
subtask1_01 AC 2 ms 384 KiB
subtask1_02 AC 2 ms 384 KiB
subtask1_03 AC 1 ms 256 KiB
subtask1_04 AC 3 ms 512 KiB
subtask1_05 AC 1 ms 256 KiB
subtask2_01 AC 2 ms 384 KiB
subtask2_02 AC 2 ms 384 KiB
subtask2_03 AC 4 ms 512 KiB
subtask2_04 AC 4 ms 640 KiB
subtask2_05 AC 1 ms 256 KiB
subtask2_06 AC 3 ms 640 KiB
subtask2_07 AC 3 ms 640 KiB
subtask3_01 AC 1 ms 256 KiB
subtask3_02 AC 1 ms 256 KiB
subtask3_03 AC 1 ms 256 KiB
subtask3_04 AC 1 ms 256 KiB
subtask3_05 AC 1 ms 256 KiB
subtask3_06 AC 1 ms 256 KiB
subtask3_07 AC 1 ms 256 KiB
subtask3_08 AC 1 ms 256 KiB
subtask3_09 AC 1 ms 256 KiB
subtask3_10 AC 1 ms 256 KiB
subtask3_11 AC 1 ms 256 KiB
subtask3_12 AC 1 ms 256 KiB
subtask4_01 AC 5 ms 384 KiB
subtask4_02 AC 3 ms 384 KiB
subtask4_03 AC 17 ms 896 KiB
subtask4_04 AC 1 ms 256 KiB
subtask4_05 AC 1 ms 256 KiB
subtask4_06 AC 3 ms 384 KiB
subtask4_07 AC 2 ms 256 KiB
subtask4_08 AC 2 ms 256 KiB
subtask4_09 AC 4 ms 384 KiB
subtask4_10 AC 2 ms 256 KiB
subtask4_11 AC 3 ms 384 KiB
subtask4_12 AC 8 ms 640 KiB
subtask5_01 AC 1023 ms 40320 KiB
subtask5_02 AC 815 ms 32256 KiB
subtask5_03 AC 1627 ms 63104 KiB
subtask5_04 AC 1 ms 256 KiB
subtask5_05 AC 2 ms 512 KiB
subtask5_06 AC 72 ms 3328 KiB
subtask5_07 AC 311 ms 16000 KiB
subtask5_08 AC 89 ms 4096 KiB
subtask5_09 AC 115 ms 5248 KiB
subtask5_10 AC 52 ms 2560 KiB
subtask5_11 AC 570 ms 24448 KiB
subtask5_12 AC 602 ms 27008 KiB
subtask5_13 AC 673 ms 63104 KiB