[20/05/17] E. MaratonIME does (not do) PAs

 

문제 푸는 중에 자꾸 deadline이 빠른 걸 고려해야 하지 않나?? 싶었는데 문제 빨리 풀어야 할 것 같아서 패스 했었다..

 

이제는 확실히 이해했음!

 

deadline 빠른 걸 고려 안 해도 되는 이유는 이미 정해져 있는 값이기 때문에 일정하다.

 

그래서 last submision time만 최소가 되게 하면 된다. 

 

int main() {
    i64 n, s;
    scanf("%lld %lld", &n, &s);
    
    vector<ii64> v(n);
    i64 end_sum = 0;
    for (int i = 0; i < n; i++)
    {
        scanf("%lld %lld", &v[i].first, &v[i].second);
        end_sum += v[i].second;
    }
    
    sort(v.begin(), v.end());
    
    i64 last_sum = 0;
    for (int i = 0; i < n; i++)
    {
        last_sum += last_sum + v[i].first;
    }
    
    printf("%lld", last_sum + n * s - end_sum);
    
    return 0;
}

 

처음 생각한 코드는 이렇다.

 

제출한 시간의 합과 deadline 합을 구한 후 빼면 되겠다 싶었다.

 

그래서 입력 받을 때 deadline 합을 구했고 정렬 후 제출한 시간의 합을 더하려 했는데 틀렸다ㅋㅋ

 

알고보니 t1 + t1 + t1 + t2 +t2 +t3 형태로 더해져야 하는데 저건 t1 + t1 + t2 +t3 형태가 된다.

 

    for (int i = 0; i < n; i++)
    {
        sum += v[i].first;
        last_sum += sum;
    }

 

그래서 이렇게 고쳤다.

 

	for (int i = 0; i < n; i++) 
    {
		sum += v[i].first;
		ans += sum - v[i].second;
	}

 

이 부분은 전에 풀었던 것처럼 하는 게 나은 것 같다.

sum으로 t1 + t2 + t3를 구하고 ans는 sum에 deadline 뺀 걸 더해나가고.