// このコードは, WA になります. // このコードの出力を見ると,それぞれのテストケースについてどのようなお菓子の食べ方が最適だったのか,そして食べられたお菓子は全部で何個だったのかが分かります. #include #include #include int n, m; long long a[1123]; long long dp[1123][2]; int count(int i, int j){ if(i == 0) return 0; if(dp[i][j] == dp[i - 1][j]){ return count(i - 1, j); }else if(std::abs(dp[i][j] - dp[i - 1][!j]) == a[i - 1]){ int tmp = count(i - 1, !j); printf("%d ", i); return ++tmp; }else{ fputs("error", stderr); exit(-1); } } int main(){ scanf("%d%d", &n, &m); for(int i = 0; i < n; ++i){ for(int j = 0; j < m; ++j){ long long tmp; scanf("%lld", &tmp); a[i] += tmp; } dp[i + 1][0] = std::max(dp[i][0], dp[i][1] - a[i]); dp[i + 1][1] = std::max(dp[i][1], dp[i][0] + a[i]); } printf("\ncount: %d / %d\n", count(n, 1), n); }