Submission #63898263

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <stdio.h>
#include <inttypes.h>
int N;
char S[512345];
uint64_t left_scores[512345];
int main(void) {
  uint64_t ans = UINT64_MAX, cur = 0;
  int i, cnt;
  if (scanf("%d", &N) != 1) return 1;
  if (scanf("%512344s", S) != 1) return 1;
  for (i = 0, cnt = 0; i < N; i++) {
    if (S[i] == '1') {
      cur += i - cnt;
      cnt++;
    }
  }
  for (i = 0; i < N; i++) {
    left_scores[i] = cur;
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

#include <stdio.h>
#include <inttypes.h>

int N;
char S[512345];

uint64_t left_scores[512345];

int main(void) {
	uint64_t ans = UINT64_MAX, cur = 0;
	int i, cnt;
	if (scanf("%d", &N) != 1) return 1;
	if (scanf("%512344s", S) != 1) return 1;
	for (i = 0, cnt = 0; i < N; i++) {
		if (S[i] == '1') {
			cur += i - cnt;
			cnt++;
		}
	}
	for (i = 0; i < N; i++) {
		left_scores[i] = cur;
		if (S[i] == '1') {
			/* 切り離す */
			cnt--;
		} else {
			/* 右に移動する */
			cur -= cnt;
		}
	}
	cur = 0;
	for (i = N - 1, cnt = 0; i >= 0; i--) {
		if (S[i] == '1') {
			cur += (N - 1 - cnt) - i;
			cnt++;
		}
	}
	for (i = N - 1; i >= 0; i--) {
		if (S[i] == '1') {
			/* 切り離す */
			cnt--;
			/* 評価する */
			if (cur + left_scores[i] < ans) ans = cur + left_scores[i];
		} else {
			/* 左に移動する */
			cur -= cnt;
		}
	}
	printf("%" PRIu64 "\n", ans == UINT64_MAX ? 0 : ans);
	return 0;
}

/*

まず、1 を全部左に寄せる
その後、右に移動していく
ただし、1 の本来の位置が左端に来たら、その1 をそこに残す

右からも同様にやる → 左右を合わせたのがそこを中心としたときのスコア

半端なところに置くより、既存の 1 どれかを中心にしたほうが不利にならないだろ (予想)

*/

Submission Info

Judge Result