Submission #6931848


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     @hamayanhamayan
    /   \     | |
    /   / ̄ ̄ ̄ ̄/  |
  __(__ニつ/     _/ .| .|____
     \/____/ (u ⊃
---------------------------------------------------------------------------------------------------*/













int N, D;
ll M[2010][2010];
ll dp[2010][2010];
//---------------------------------------------------------------------------------------------------
ll get(int day, int moved) {
	ll tot = M[day - 1][N - 1];
	ll R = 0;
	if(0 < moved) R = M[day - 1][moved - 1];
	ll L = tot - R;

	return abs(R - L);
}
//---------------------------------------------------------------------------------------------------
void _main() {
	cin >> N >> D;
	rep(i, 0, D) rep(j, 0, N) cin >> M[i][j];
	rep(i, 0, D) rep(j, 1, N) M[i][j] += M[i][j - 1];

	rep(day, 0, D + 1) rep(moved, 0, N + 1) dp[day][moved] = infl;
	dp[0][0] = 0;

	rep(day, 1, D + 1) {
		ll mi = infl;
		rep(moved, 0, N + 1) {
			chmin(mi, dp[day - 1][moved]);
			chmin(dp[day][moved], mi + get(day, moved));
		}
	}

	ll ans = infl;
	rep(moved, 0, N + 1) chmin(ans, dp[D][moved]);
	cout << ans << endl;
}






Submission Info

Submission Time
Task F - 天秤とコイン (Balance and Coins)
User hamayanhamayan
Language C++14 (GCC 5.4.1)
Score 100
Code Size 2168 Byte
Status AC
Exec Time 406 ms
Memory 63232 KB

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 2 ms 2304 KB
sample_02 AC 2 ms 2304 KB
sample_03 AC 2 ms 2304 KB
subtask1_01 AC 5 ms 19200 KB
subtask1_02 AC 7 ms 27392 KB
subtask1_03 AC 3 ms 11008 KB
subtask1_04 AC 14 ms 60544 KB
subtask1_05 AC 2 ms 2304 KB
subtask2_01 AC 8 ms 29440 KB
subtask2_02 AC 8 ms 31488 KB
subtask2_03 AC 13 ms 56064 KB
subtask2_04 AC 14 ms 60544 KB
subtask2_05 AC 2 ms 2304 KB
subtask2_06 AC 14 ms 60544 KB
subtask2_07 AC 14 ms 60544 KB
subtask3_01 AC 2 ms 2304 KB
subtask3_02 AC 2 ms 2304 KB
subtask3_03 AC 2 ms 2304 KB
subtask3_04 AC 2 ms 2304 KB
subtask3_05 AC 2 ms 2304 KB
subtask3_06 AC 2 ms 2304 KB
subtask3_07 AC 2 ms 2304 KB
subtask3_08 AC 2 ms 2304 KB
subtask3_09 AC 2 ms 2304 KB
subtask3_10 AC 2 ms 2304 KB
subtask3_11 AC 2 ms 2304 KB
subtask3_12 AC 2 ms 2304 KB
subtask4_01 AC 3 ms 2688 KB
subtask4_02 AC 3 ms 4992 KB
subtask4_03 AC 7 ms 7168 KB
subtask4_04 AC 2 ms 2304 KB
subtask4_05 AC 3 ms 6912 KB
subtask4_06 AC 3 ms 6912 KB
subtask4_07 AC 2 ms 2432 KB
subtask4_08 AC 3 ms 6912 KB
subtask4_09 AC 3 ms 4864 KB
subtask4_10 AC 2 ms 2688 KB
subtask4_11 AC 3 ms 6912 KB
subtask4_12 AC 5 ms 7040 KB
subtask5_01 AC 264 ms 62848 KB
subtask5_02 AC 213 ms 57216 KB
subtask5_03 AC 406 ms 63232 KB
subtask5_04 AC 2 ms 2304 KB
subtask5_05 AC 14 ms 60544 KB
subtask5_06 AC 26 ms 31744 KB
subtask5_07 AC 87 ms 20736 KB
subtask5_08 AC 33 ms 41984 KB
subtask5_09 AC 36 ms 23808 KB
subtask5_10 AC 17 ms 9600 KB
subtask5_11 AC 171 ms 56960 KB
subtask5_12 AC 166 ms 30976 KB
subtask5_13 AC 249 ms 63232 KB