Algoogle

Algorithm for Programming Contest

PKU 2393 Yogurt factory

Category: PKU Tag: greedy

Yogurt factory

問題概要


解法


使う価格を保存しておいて毎週かかるお金と比較して, 小さい方を使う価格として更新する.

コード


(2393.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <algorithm>
#include <cstdio>

using namespace std;

int N, S, C, Y, P;
//int C[10010], Y[10010];

int main(){
    scanf("%d%d", &N, &S);

    P = int(1e9);
    long long ans = 0;
    for(int i = 0; i < N; i++){
        scanf("%d%d", &C, &Y);
        P = min(P + S, C);
        ans += P * Y;
    }
    printf("%lld\n", ans);
    return 0;
}

Comments