| # | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 333605 | 2020-12-07T07:48:48 Z | tengiz05 | Money (IZhO17_money) | C++17 | 865 ms | 492 KB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
#define all(x) (x).begin(), (x).end()
#define pb push_back
#define pii pair<int, int>
#define ff first
#define ss second
#define PI acos(-1)
#define ld long double
const int mod = 1e9+7, N = 1e6+5;
int msb(int val){return sizeof(int)*8-__builtin_clzll(val);}
int a[N], n, m, k;
int f(int n){
int i, j;
set<int> s;
s.insert(mod);
int ans = 0;
for(i=1;i<=n;i++){
ans++;
j = i;
int need = *s.upper_bound(a[i]);
s.insert(a[i]);
while(i+1 <= n && a[i+1] >= a[i] && a[i+1] < need){
i++;
s.insert(a[i]);
}
}
return ans;
}
int f1(int n){
int i, j;
int ans = mod;
vector<int> v;
for(i=1;i<=n;i++)v.pb(a[i]);
for(int mask = 0; mask < (1<<n); mask++){
set<int> s;
s.insert(mod);
int tt = 0;
for(i=0;i<n;i++){
tt++;
int need = *s.upper_bound(v[i]);
s.insert(v[i]);
int cnt =1;
while(i+1 < n && (((mask&(1<<i)) && (mask&(1<<(i+1)))) || (!(mask&(1<<i)) && (!(mask&(1<<(i+1))))))){
if(v[i+1] < v[i])tt = mod;
i++;
if(v[i] > need)tt = mod;
s.insert(v[i]);cnt++;
}
}ans = min(ans, tt);
// cout << mask << ' ' << tt << '\n';
}
assert(ans != mod);
return ans;
}
/*
7
1 5 7 2 3 4 6
* */
void solve(int test_case){
int i, j;
cin >> n;
for(i=1;i<=n;i++){
cin >> a[i];
}
cout << f1(n) << '\n';
}
signed main(){
FASTIO;
#define MULTITEST 0
#if MULTITEST
int ___T;
cin >> ___T;
for(int T_CASE = 1; T_CASE <= ___T; T_CASE++)
solve(T_CASE);
#else
solve(1);
#endif
return 0;
}
Compilation message
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 364 KB | Output is correct |
| 2 | Correct | 1 ms | 364 KB | Output is correct |
| 3 | Correct | 1 ms | 364 KB | Output is correct |
| 4 | Correct | 1 ms | 364 KB | Output is correct |
| 5 | Correct | 1 ms | 364 KB | Output is correct |
| 6 | Correct | 1 ms | 384 KB | Output is correct |
| 7 | Correct | 1 ms | 364 KB | Output is correct |
| 8 | Correct | 1 ms | 384 KB | Output is correct |
| 9 | Correct | 1 ms | 384 KB | Output is correct |
| 10 | Correct | 1 ms | 364 KB | Output is correct |
| 11 | Correct | 1 ms | 364 KB | Output is correct |
| 12 | Correct | 1 ms | 364 KB | Output is correct |
| 13 | Correct | 1 ms | 364 KB | Output is correct |
| 14 | Correct | 1 ms | 364 KB | Output is correct |
| 15 | Correct | 1 ms | 384 KB | Output is correct |
| 16 | Correct | 1 ms | 364 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 364 KB | Output is correct |
| 2 | Correct | 1 ms | 364 KB | Output is correct |
| 3 | Correct | 1 ms | 364 KB | Output is correct |
| 4 | Correct | 1 ms | 364 KB | Output is correct |
| 5 | Correct | 1 ms | 364 KB | Output is correct |
| 6 | Correct | 1 ms | 384 KB | Output is correct |
| 7 | Correct | 1 ms | 364 KB | Output is correct |
| 8 | Correct | 1 ms | 384 KB | Output is correct |
| 9 | Correct | 1 ms | 384 KB | Output is correct |
| 10 | Correct | 1 ms | 364 KB | Output is correct |
| 11 | Correct | 1 ms | 364 KB | Output is correct |
| 12 | Correct | 1 ms | 364 KB | Output is correct |
| 13 | Correct | 1 ms | 364 KB | Output is correct |
| 14 | Correct | 1 ms | 364 KB | Output is correct |
| 15 | Correct | 1 ms | 384 KB | Output is correct |
| 16 | Correct | 1 ms | 364 KB | Output is correct |
| 17 | Correct | 13 ms | 364 KB | Output is correct |
| 18 | Correct | 8 ms | 364 KB | Output is correct |
| 19 | Correct | 1 ms | 364 KB | Output is correct |
| 20 | Correct | 432 ms | 492 KB | Output is correct |
| 21 | Correct | 560 ms | 492 KB | Output is correct |
| 22 | Correct | 340 ms | 492 KB | Output is correct |
| 23 | Correct | 396 ms | 364 KB | Output is correct |
| 24 | Correct | 372 ms | 492 KB | Output is correct |
| 25 | Correct | 865 ms | 400 KB | Output is correct |
| 26 | Correct | 763 ms | 400 KB | Output is correct |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 364 KB | Output is correct |
| 2 | Correct | 1 ms | 364 KB | Output is correct |
| 3 | Correct | 1 ms | 364 KB | Output is correct |
| 4 | Correct | 1 ms | 364 KB | Output is correct |
| 5 | Correct | 1 ms | 364 KB | Output is correct |
| 6 | Correct | 1 ms | 384 KB | Output is correct |
| 7 | Correct | 1 ms | 364 KB | Output is correct |
| 8 | Correct | 1 ms | 384 KB | Output is correct |
| 9 | Correct | 1 ms | 384 KB | Output is correct |
| 10 | Correct | 1 ms | 364 KB | Output is correct |
| 11 | Correct | 1 ms | 364 KB | Output is correct |
| 12 | Correct | 1 ms | 364 KB | Output is correct |
| 13 | Correct | 1 ms | 364 KB | Output is correct |
| 14 | Correct | 1 ms | 364 KB | Output is correct |
| 15 | Correct | 1 ms | 384 KB | Output is correct |
| 16 | Correct | 1 ms | 364 KB | Output is correct |
| 17 | Correct | 13 ms | 364 KB | Output is correct |
| 18 | Correct | 8 ms | 364 KB | Output is correct |
| 19 | Correct | 1 ms | 364 KB | Output is correct |
| 20 | Correct | 432 ms | 492 KB | Output is correct |
| 21 | Correct | 560 ms | 492 KB | Output is correct |
| 22 | Correct | 340 ms | 492 KB | Output is correct |
| 23 | Correct | 396 ms | 364 KB | Output is correct |
| 24 | Correct | 372 ms | 492 KB | Output is correct |
| 25 | Correct | 865 ms | 400 KB | Output is correct |
| 26 | Correct | 763 ms | 400 KB | Output is correct |
| 27 | Runtime error | 11 ms | 492 KB | Execution killed with signal 6 (could be triggered by violating memory limits) |
| 28 | Halted | 0 ms | 0 KB | - |
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| 1 | Correct | 1 ms | 364 KB | Output is correct |
| 2 | Correct | 1 ms | 364 KB | Output is correct |
| 3 | Correct | 1 ms | 364 KB | Output is correct |
| 4 | Correct | 1 ms | 364 KB | Output is correct |
| 5 | Correct | 1 ms | 364 KB | Output is correct |
| 6 | Correct | 1 ms | 384 KB | Output is correct |
| 7 | Correct | 1 ms | 364 KB | Output is correct |
| 8 | Correct | 1 ms | 384 KB | Output is correct |
| 9 | Correct | 1 ms | 384 KB | Output is correct |
| 10 | Correct | 1 ms | 364 KB | Output is correct |
| 11 | Correct | 1 ms | 364 KB | Output is correct |
| 12 | Correct | 1 ms | 364 KB | Output is correct |
| 13 | Correct | 1 ms | 364 KB | Output is correct |
| 14 | Correct | 1 ms | 364 KB | Output is correct |
| 15 | Correct | 1 ms | 384 KB | Output is correct |
| 16 | Correct | 1 ms | 364 KB | Output is correct |
| 17 | Correct | 13 ms | 364 KB | Output is correct |
| 18 | Correct | 8 ms | 364 KB | Output is correct |
| 19 | Correct | 1 ms | 364 KB | Output is correct |
| 20 | Correct | 432 ms | 492 KB | Output is correct |
| 21 | Correct | 560 ms | 492 KB | Output is correct |
| 22 | Correct | 340 ms | 492 KB | Output is correct |
| 23 | Correct | 396 ms | 364 KB | Output is correct |
| 24 | Correct | 372 ms | 492 KB | Output is correct |
| 25 | Correct | 865 ms | 400 KB | Output is correct |
| 26 | Correct | 763 ms | 400 KB | Output is correct |
| 27 | Runtime error | 11 ms | 492 KB | Execution killed with signal 6 (could be triggered by violating memory limits) |
| 28 | Halted | 0 ms | 0 KB | - |