Районная олимпиада по информатике. 2008-2009 учебный год.

Задача C. Выгода

Ограничение по времени:

2 seconds

Ограничение по памяти:

64 megabytes

Компьютер состоит из процессорного блока и монитора. На складе имеется $N$ системных блоков и $M$ мониторов. i-й блок стоит $A_i$ тугриков, j-й монитор – $B_j$ тугриков. Из-за мирового финансового кризиса, стоимость компьютера, в состав которого входит i-й системный блок и j-й монитор равна $A_i$ ∙ $B_j$ (умножение) тугриков. Вам надо собрать наибольшее возможное количество компьютеров так, чтобы их суммарная стоимость была максимально возможной.

Формат входного файла

Первая строка входного файла содержит два целых числа: $N$ и $M$ ($1 <= N, M <= 1000$). Вторая строка содержит $N$ целых чисел: i-е число в строке – это $A_i$. Третья строка содержит $M$ целых чисел: j-е число в строке – это $B_j$. ($1 <= A_i, B_j <= 1000$). Числа в строках разделены пробелами.

Формат выходного файла

Выходной файл должен содержать два целых числа, разделенных пробелом – максимально возможное число компьютеров и их максимальную суммарную стоимость.

Примеры:

Вход

3 2
1 2 3
4 5

Ответ

2 23

Комментарий/решение

показать/скрыть код

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n,m;
    cin >> n >> m;
    int a[n],b[m];
    for (int i=0; i<n; i++) cin >> a[i];
    for (int i=0; i<m; i++) cin >> b[i];
    sort(a,a+n);
    sort(b,b+m);
    int k = min(n,m);
    cout << k << ' ';
    int sum=0;
    for (int i=1; i<=k; i++) {
        sum += a[n-i] * b[m-i];
    }
    cout << sum;
}

C++

Copy

DELETED

#include<bits/stdc++.h>

using namespace std;

int main()

{

ios_base::sync_with_stdio;

cin.tie(0);

cout.tie(0);

int cal=0;

int n,m;

cin>>n>>m;

vector <int> vec1;

vector <int> vec2;

for(int i=0;i<n;i++)

{

int a;

cin>>a;

vec1.push_back(a);

}

sort(vec1.begin(),vec1.end());

for(int i=0;i<m;i++)

{

int a;

cin>>a;

vec2.push_back(a);

}

sort(vec2.begin(),vec2.end());

if(vec1.size()>vec2.size())

{

while(vec1.size()>vec2.size()){

int i=0;

vec1.erase(vec1.begin() + 0);

}

for(int i=0;i<vec1.size();i++){

cal=cal+vec1[i]*vec2[i];

}

cout<<vec1.size()<<" "<<cal;

}

else if(vec2.size()>vec1.size())

{

while(vec2.size()>vec1.size()){

int i=0;

vec2.erase(vec2.begin() + 0);

}

for(int i=0;i<vec2.size();i++){

cal=cal+vec2[i]*vec1[i];

}

cout<<vec1.size()<<" "<<cal;

}

else

{

for(int i=0;i<vec2.size();i++){

cal=cal+vec2[i]*vec1[i];

}

cout<<vec1.size()<<" "<<cal;

}

}

показать/скрыть код

#include <bits/stdc++.h>
using namespace std;
int n,m,sum=0;
int main(){
    cin>>n>>m;
    int a[1025],b[1025];
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    for(int i=1;i<=m;i++){
        cin>>b[i];
    }
    sort(a+1,a+n+1);
    sort(b+1,b+m+1);
    reverse(a+1,a+n+1);
    reverse(b+1,b+m+1);
    for(int i=1;i<=min(n,m);i++){
        sum+=a[i]*b[i];
    }
    cout<<min(n,m)<<' '<<sum<<endl;
    }

C++

Copy