oj.uz

Submission #338181

# Submission time Handle Problem Language Result Execution time Memory
338181 2020-12-22T15:53:24 Z talant117408 Skyline (IZhO11_skyline) C++17
100 / 100
 234 ms 112280 KB 
/*
    Code written by Talant I.D.
*/
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include <ext/rope>
//#include <ext/pb_ds/assoc_container.hpp>
 
//using namespace __gnu_pbds;
using namespace __gnu_cxx;
using namespace std;
 
//typedef tree <int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
  
#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define OK cout << "OK" << endl;
  
inline bool isvowel(char ch){
    ch = tolower(ch);
    return (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u');
}
  
inline bool isprime(int n){
    if(n < 2 || (n%2 == 0 && n != 2)) return false;
    for(int i = 3; i*i <= n; i++)
        if(n%i == 0) return false;
    return true;
}
 
class Union{
    private:
        vector <int> saizu, link;
    public:
        Union(int n){
            saizu.assign(n, 1); link.resize(n); 
            iota(all(link), 0);
        }
        int find(int n){
            if(link[n] == n) return n;
            return link[n] = find(link[n]);
        }
        int same(int a, int b){
            return find(a) == find(b);
        }
        void unite(int a, int b){
            if(same(a, b)) return;
             
            a = find(a); b = find(b);
            if(saizu[a] < saizu[b]) swap(a, b);
             
            saizu[a] += saizu[b];
            link[b] = a;
        }
        int getsize(int a){
            return saizu[find(a)];
        }
};
 
const int mod = 1e9+7;
 
ll mode(ll a){
    a %= mod;
    if(a < 0) a += mod;
    return a;
}
 
ll subt(ll a, ll b){
    return mode(mode(a)-mode(b));
}
 
ll add(ll a, ll b){
    return mode(mode(a)+mode(b));
}
 
ll mult(ll a, ll b){
    return mode(mode(a)*mode(b));
}
 
ll binpow(ll a, ll b){
    ll res = 1;
    while(b){
        if(b&1) res = mult(res, a);
        a = mult(a, a);
        b >>= 1;
    }
    return res;
}

const int N = 305;
int dp[N][N][N], n;
int v[N];

int rec(int pos, int x, int y){
    if(pos >= n){
        return min(x, y)*5+(max(x, y)-min(x, y))*3;
    }
    int &res = dp[pos][x][y];
    
    if(res != 2e9){
        return res;
    }
    
    if(x == min(min(x, y), v[pos])){
        res = min(res, rec(pos+1, y-x, v[pos]-x)+x*7);
    }
    if(x > 0 && y > 0){
        res = min(res, rec(pos, x-1, y-1)+5);
    }
    if(x > 0){
        res = min(res, rec(pos, x-1, y)+3);
    }
    return res;
}

int main(){
    do_not_disturb
    
    cin >> n;
    for(int i = 0; i < n; i++){
        cin >> v[i];
    }
    
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            for(int l = 0; l < N; l++){
                dp[i][j][l] = 2e9;
            }
        }
    }
    cout << rec(2, v[0], v[1]);
    
    return 0;
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 111340 KB Output is correct
2 Correct 56 ms 111340 KB Output is correct
3 Correct 60 ms 111488 KB Output is correct
4 Correct 54 ms 111340 KB Output is correct
5 Correct 54 ms 111468 KB Output is correct
6 Correct 54 ms 111340 KB Output is correct
7 Correct 56 ms 111468 KB Output is correct
8 Correct 54 ms 111340 KB Output is correct
9 Correct 55 ms 111468 KB Output is correct
10 Correct 57 ms 111468 KB Output is correct
11 Correct 72 ms 111852 KB Output is correct
12 Correct 59 ms 111468 KB Output is correct
13 Correct 73 ms 111980 KB Output is correct
14 Correct 87 ms 112108 KB Output is correct
15 Correct 182 ms 112108 KB Output is correct
16 Correct 164 ms 112108 KB Output is correct
17 Correct 233 ms 111468 KB Output is correct
18 Correct 221 ms 111852 KB Output is correct
19 Correct 211 ms 112280 KB Output is correct
20 Correct 234 ms 111980 KB Output is correct