oj.uz

Submission #502177

# Submission time Handle Problem Language Result Execution time Memory
502177 2022-01-05T12:15:59 Z khangal Skyline (IZhO11_skyline) C++14
100 / 100
 231 ms 127744 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef double db;
typedef vector<long long> vl;
typedef pair<long long, long long > pl;
const int N = 1e6 + 1;
#define po pop_back
#define pb push_back
#define mk make_pair
#define lw lower_bound
#define up upper_bound
#define ff first
#define ss second
#define boost ios_base::sync_with_stdio(); cin.tie(0); cout.tie(0);
#define MOD 1000000007
#define MAX 1e18 
#define MIN -1e18
#define per(i,a,b) for(ll i=b;i>=a;i--)
#define con continue
#define freopen freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define PI 3.14159265358979323846264338327950288419716939937510582097494459230781640628
//typedef tree<ll , null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set;
template< typename T>
using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
ll n, m, ans, mid, mn, mx, cnt, sum, h1, h2, arr[3234567],arr1[1234567], sz, k, i, j, h, a, w, x, y, z,par[1234567];
bool used[1234567];
ll dx[4]={-1,1,0,0},dy[4]={0,0,-1,1},c1[123][123];
vector<ll> edge[1234567];
ll jump[22][223456];
ll lvl[1234567];
//ll bit[1234567];
//ll timer;
//ll st[1234567],endd[1234567];
//ll dp[5005][5005];
ll power(ll base, ll val, ll mod) {
    ll res = 1;
    while (val) {
        if (val % 2 == 1) {
            res = res * base;
        }
        base = base * base;
        base %= mod;
        res %= mod;
        val /= 2;
    }
    return res;
}
bool comp(pl x,pl y){
    if(x.ff>y.ff)return true;
    return false;
}
ll find(ll x){
    if(x==par[x])return x;
    else return par[x]=find(par[x]);
}
void process_LCA(){
    for(int i=1;(1<<i)<=n;i++){
        for(int j=1;j<=n;j++){
            jump[i][j] = jump[i-1][jump[i-1][j]];
        }
    }
}
ll LCA(ll x,ll y){
    if(lvl[x] < lvl[y])swap(x,y);
    ll diss = lvl[x] - lvl[y];
    for(int i=21;i>=0;i--){
        if((1<<i)&diss){
            x = jump[i][x];
        }
    }
    if(x==y)return x;
    for(int i=21;i>=0;i--){
        if(jump[i][x] != jump[i][y]){
            x = jump[i][x];
            y = jump[i][y];
        }
    }
    return jump[0][x];
}
ll dp[305][205][205];
ll rec(ll pos,ll x,ll y){
    if(pos > n){
        return 5*min(x,y) + 3*abs(x-y);
    }
    if(dp[pos][x][y]!=MAX)return dp[pos][x][y];
    ll val = min({arr[pos],x,y});
    if(val == x){
        dp[pos][x][y] = min(dp[pos][x][y] , rec(pos+1 , y-val , arr[pos] - val) + 7*val);   
    }
    if(x && y){
        dp[pos][x][y] = min(dp[pos][x][y] , rec(pos,x-1,y-1) + 5);
    }
    if(x){
        dp[pos][x][y] = min(dp[pos][x][y] , rec(pos,x-1,y) + 3);        
    }
    return dp[pos][x][y];
}
class A {
public:
    static void funcA() {
        cin>>n;
        for(int i=1;i<=n;i++){cin>>arr[i];}
        for(int i=1;i<=300;i++)for(int j=0;j<=200;j++)for(int k=0;k<=200;k++)dp[i][j][k]=MAX;
        cout<<rec(3,arr[1],arr[2]);
    }
}lol;
void solve() {
    A::funcA();
}
int main() {
    ll T = 1;
    //cin>>T;
    boost;
    while (T--) {
        solve();
    }
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 127308 KB Output is correct
2 Correct 55 ms 127172 KB Output is correct
3 Correct 56 ms 127164 KB Output is correct
4 Correct 55 ms 127248 KB Output is correct
5 Correct 52 ms 127248 KB Output is correct
6 Correct 52 ms 127204 KB Output is correct
7 Correct 53 ms 127212 KB Output is correct
8 Correct 54 ms 127192 KB Output is correct
9 Correct 57 ms 127192 KB Output is correct
10 Correct 57 ms 127272 KB Output is correct
11 Correct 66 ms 127504 KB Output is correct
12 Correct 56 ms 127312 KB Output is correct
13 Correct 69 ms 127468 KB Output is correct
14 Correct 78 ms 127616 KB Output is correct
15 Correct 171 ms 127708 KB Output is correct
16 Correct 150 ms 127684 KB Output is correct
17 Correct 231 ms 127272 KB Output is correct
18 Correct 217 ms 127552 KB Output is correct
19 Correct 204 ms 127744 KB Output is correct
20 Correct 207 ms 127460 KB Output is correct