Решение задачи Опять ограничения с Codeforces

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


Вы планируете строить дома на улице. На улице есть n мест, где вы можете построить дома. Эти места пронумерованы слева направо от 1 до n. В каждом месте вы можете построить дом с целочисленной высотой от 0 до h.

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

Город имеет m ограничений. В соответствии с i-м ограничением, самый высокий дом от li до ri (включительно) должен иметь высоту не более xi.

Код

#include <bits/stdc++.h>

using namespace std;

int main()
{
    int n, h, m, l, r, x;
    cin >> n >> h >> m;
    vector<int> a(n, h);
    for(int i = 0; i < m; ++i){
        cin >> l >> r >> x;
        for(int i = l ; i <= r; ++i)
            if(a[i - 1] > x)
                a[i - 1] = x;

    }
    sort(a.begin(), a.end());
    int res = 0;
    for(int i = 0; i < n; ++i){
        res+=a[a.size() - 1 - i] * a[a.size() - 1 - i];
    }
    cout << res;
    return 0;
}

         

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


Код

n,h,m=map(int,input().split())
arr=[h**2]*n
for i in range(m):
    a,b,c=map(int,input().split())
    for j in range(a-1,b):
        arr[j]=min(arr[j],c**2)
print(sum(arr))

         

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




Комментарии

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