oj.uz

Submission #692314

# Submission time Handle Problem Language Result Execution time Memory
692314 2023-02-01T10:45:42 Z saayan007 Mountains (IOI17_mountains) C++17
0 / 100
 49 ms 276 KB 
#include "mountains.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pi = pair<int, int>;
using pl = pair<long long, long long>;
using vi = vector<int>;
using vl = vector<long long>;
using vpi = vector<pair<int, int>>;
using vpl = vector<pair<long long, long long>>;

#define fur(i, a, b) for(ll i = a; i <= (ll)b; ++i)
#define ruf(i, a, b) for(ll i = a; i >= (ll)b; --i)
#define fr first 
#define sc second
#define mp make_pair
#define pb emplace_back
#define nl "\n"
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

int n;
bool check(int bit, vector<int> &y) {
    bool d[n] = {};
    for(int i = 0; i < n; ++i) {
        d[i] = (bit & (1 << i));
    }

    for(int i = 0; i < n; ++i) {
        if(!d[i])
            continue;
        for(int j = i + 1; j < n; ++j) {
            if(!d[j])
                continue;
            bool block = 0;
            for(int k = i + 1; k <= j - 1; ++k) {
                if(i * (y[k] - y[j]) + k * (y[j] - y[i]) + j * (y[i] - y[k]) < 0) {
                    block = 1;
                }
            }
            if(!block)
                return 0;
        }
    }
    return 1;
}

int maximum_deevs(vector<int> y) {
    int ans = 1;
    n = y.size();
    for(int i = 0; i < (1 << n); ++i) {
        if(check(i, y)) {
            ans = max(ans, __builtin_popcount(i));
        }
    }

    return ans;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Incorrect 49 ms 276 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Incorrect 49 ms 276 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Incorrect 49 ms 276 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Incorrect 49 ms 276 KB Output isn't correct
7 Halted 0 ms 0 KB -