어떤 문제인가?

전형적인 그리디 알고리즘 문제다. 최소값만 꽁무니 빠지게 찾아다니면 된다.

난 C로 못하겠어요

대충 최대값이 얼마나 나올지 계산을 해봤는데,

• 최대 기름값 10^9
• 최대 도시 간 거리 10^9
• 최대 테스트케이스 수 10^6

다 곱하면 10^24이 나오는데, unsigned long long으로도 감당이 안되는 수치다.
큰 수를 배열로 표현해서 덧셈을 구현하려고 했는데, 이게 생각보다 정신력을 심하게 갉아먹는 짓거리였다.
이딴 거 생각할 바에 그냥 푸는 게 낫다고 생각해서 파이썬으로 풀었다. long 타입은 컴퓨터가 받쳐줄 수 있는 한 무한의 길이를 가지니까.

import sys

W, A = [], [];
S, m = 0, 0
input()
W = list(map(int, sys.stdin.readline().split()))
A = list(map(int, sys.stdin.readline().split()))
m = A[0]
for i in range(0, len(W)):
    S += m*W[i]
    if m > A[i+1]:
        m = A[i+1]
print(S)

님 그거 어캐함???

파이썬으로 문제를 풀고 C언어로 어떻게 문제를 풀었는지 확인했다. 아니 근데 이게 됐네???

#include <stdio.h>

int d[100000];

int main()
{
	int n, min_f = 1000000000;
	int fuel;
	unsigned long long total_sum = 0;

	scanf("%d", &n);
	for(int i=0;i<n-1;i++)
		scanf("%d", &d[i]);
	for (int i = 0; i < n - 1; i++)
	{
		scanf("%d", &fuel);
		if (fuel < min_f)
			min_f = fuel;
		total_sum += min_f * 1LL * d[i];
	}
	printf("%llu", total_sum);
}

joystic1234님 코드
-> https://www.acmicpc.net/source/24958894

괜히 쫄았다. 나중에 풀 때는 안 돼도 한번이라도 비벼보자.