# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
977437 | shoryu386 | Money (IZhO17_money) | C++17 | 18 ms | 24156 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define int long long
main(){ ios_base::sync_with_stdio(0); cin.tie(0);
int n; cin >> n;
//attempt greedy
int arr[n]; for (int x = 0; x < n; x++) cin >> arr[x];
vector<int> dc[1000007];
for (int x = 0; x < n; x++){
dc[arr[x]].push_back(x);
}
for (int x = 0; x < n; x++){
}
bitset<1000007> taken;
set<int> valuesTaken;
for (int zzz = 1; zzz <= n; zzz++){
int smallestVal = LLONG_MAX/20, smIndex = -1;
for (int x = 0; x < n; x++){
if (!taken[x] && smallestVal > arr[x]){
smallestVal = arr[x];
smIndex = x;
}
}
int lastVal = arr[smIndex];
taken[smIndex] = 1; vector<int> newval;
for (int z = smIndex+1; z < n; z++){
if (taken[z] || lastVal > arr[z]) break;
bool die = false;
for (auto y : valuesTaken){
if (lastVal <= y && y < arr[z]){
die = true;
break;
}
}
if (die) break;
taken[z] = 1;
lastVal = arr[z];
newval.push_back(arr[z]);
}
for (auto y : newval){
valuesTaken.insert(y);
}
bool allTaken = true;
for (int x = 0; x < n; x++) if (!taken[x]) allTaken = false;
if (allTaken){
cout << zzz;
return 0;
}
}
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |