| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1281664 | dimitri.shengelia | 축제 (IOI25_festival) | C++20 | 0 ms | 0 KiB |
#include "festival.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> max_coupons(long long A, vector<long long> P, vector<long long> T) {
int n = P.size();
vector <int> v;
multiset <pair <long long, int>> st1, st2, st3, st4;
for ( int i = 0; i < n; i++ ) {
if ( T[i] == 1 ) {
st1.insert( { P[i], i } );
} else if ( T[i] == 2 ) {
st2.insert( { P[i] * 2, i } );
} else if ( T[i] == 3 ) {
st3.insert( { P[i] * 3, i } );
} else {
st4.insert( { P[i] * 4, i } );
}
}
while ( A >= 0 ) {
long long mx = -1;
long long a1 = 0, a2 = 0, a3 = 0, a4 = 0;
if ( st1.size() > 0 ) {
a1 = A - st1.begin()->first;
mx = a1;
}
if ( st2.size() > 0 ) {
a2 = A * 2 - st2.begin()->first;
mx = max( mx, a2 );
}
if ( st3.size() > 0 ) {
a3 = A * 3 - st3.begin()->first;
mx = max( mx, a3 );
}
if ( st4.size() > 0 ) {
a4 = A * 4 - st4.begin()->first;
mx = max( mx, a4 );
}
if ( mx < 0 ) {
break;
} else if ( st1.size() > 0 and a1 == mx ) {
v.push_back( st1.begin()->second );
st1.erase( st1.begin() );
A = a1;
} else if ( st2.size() > 0 and a2 == mx ) {
v.push_back( st2.begin()->second );
st2.erase( st2.begin() );
A = a2;
} else if ( st3.size() > 0 and a3 == mx ) {
v.push_back( st3.begin()->second );
st3.erase( st3.begin() );
A = a3;
} else if ( st4.size() > 0 and a4 == mx ) {
v.push_back( st4.begin()->second );
st4.erase( st4.begin() );
A = a4;
}
}
return v;
}
/*int main() {
long long n, a;
cin >> n >> a;
vector <long long> p, t;
for ( int i = 0; i < n; i++ ) {
long long x;
cin >> x;
p.push_back( x );
}
for ( int i = 0; i < n; i++ ) {
long long x;
cin >> x;
t.push_back( x );
}
vector <int> answer = max_coupons( a, p, t );
cout << answer.size() << "\n";
for ( int i = 0; i < answer.size() - 1; i++ ) {
cout << answer[i] << " ";
}
if ( answer.size() > 0 ) {
cout << answer[answer.size() - 1] << "\n";
}
return 0;
}*/