Решение задачи Шоколадки с Codeforces

Без пояснения   Просмотров: 22


Вы пришли в магазин, продающих n типов шоколадок. Всего в наличии есть ai шоколадок типа i.

У вас есть неограниченное количество денег (так что никаие цены не являются ограничивающим фактором) и вы хотите купить как можно больше шоколадок. Однако, если вы купите xi шоколадок типа i (очевидно, 0≤xi≤ai), то для каждого 1≤j
xj=0 (вы купили ноль шоколадок типа j)
xj Например, массив x=[0,0,1,2,10] удовлетворяет условию выше (в предположении, что все ai≥xi), а массивы x=[0,1,0], x=[5,5] и x=[3,2] нет.

Вычислите наибольшое количество шоколадок, которое вы можете купить.


Код

#include <bits/stdc++.h>
using namespace std;
int a[200005];
int main(){
	int N; scanf("%d",&N);
	for(int i=N-1; i>=0; --i) scanf("%d",a+i);
	long long ans = a[0];
	int t = a[0];
	for(int i=1; i<N; ++i){
		if(t) t = min(t-1, a[i]);
		ans += t;
	}
	printf("%lld",ans);
	return 0;
}

         

Администратор Photo Автор: Администратор



Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться