oj.uz

Submission #475041

# Submission time Handle Problem Language Result Execution time Memory
475041 2021-09-20T18:03:52 Z nicolaalexandra Secret (JOI14_secret) C++14
100 / 100
 580 ms 8384 KB 
#include <bits/stdc++.h>
#define DIM 1010
#define INF 1000000000
#include "secret.h"
using namespace std;

int n,i,j;
int v[DIM],a[DIM],dp[DIM][DIM];
/*
int Secret (int x, int y){
    return min (x + 2 * (y / 2), INF);
}
*/
void solve (int st, int dr){
    if (dr - st <= 1)
        return;
    int mid = (st+dr)>>1;
    solve (st,mid);
    solve (mid+1,dr);

    for (int i=mid-1;i>=st;i--)
        if (dp[i][mid] == -1)
            dp[i][mid] = Secret (v[i],dp[i+1][mid]);

    for (int i=mid+2;i<=dr;i++)
        if (dp[mid+1][i] == -1)
            dp[mid+1][i] = Secret (dp[mid+1][i-1],v[i]);
}

void Init (int _n, int a[]){
    n = _n;
    for (i=0;i<n;i++)
        v[i+1] = a[i];

    for (i=1;i<=n;i++){
        dp[i][i] = v[i];
        for (j=i+1;j<=n;j++)
            dp[i][j] = -1;
    }

    solve (1,n);
}

int Query (int l, int r){
    l++, r++;
    if (l == r)
        return v[l];

    if (r - l == 1)
        return Secret (v[l],v[r]);


    for (i=l;i<r;i++){
        if (dp[l][i] != -1 && dp[i+1][r] != -1)
            return Secret(dp[l][i],dp[i+1][r]);
    }
}

/*
int main (){

    ifstream cin ("date.in");
    ofstream cout ("date.out");

    int n,q,i,x,y;

    cin>>n;
    for (i=0;i<n;i++)
        cin>>a[i];

    Init (n,a);

    cin>>q;
    for (;q--;){
        cin>>x>>y;
        cout<<Query(x,y)<<"\n";
    }


    return 0;
}
*/

Compilation message

secret.cpp: In function 'int Query(int, int)':
secret.cpp:57:1: warning: control reaches end of non-void function [-Wreturn-type]
   57 | }
      | ^

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 147 ms 4524 KB Output is correct - number of calls to Secret by Init = 3084, maximum number of calls to Secret by Query = 1
2 Correct 154 ms 4488 KB Output is correct - number of calls to Secret by Init = 3092, maximum number of calls to Secret by Query = 1
3 Correct 170 ms 4408 KB Output is correct - number of calls to Secret by Init = 3101, maximum number of calls to Secret by Query = 1
4 Correct 534 ms 8208 KB Output is correct - number of calls to Secret by Init = 6989, maximum number of calls to Secret by Query = 1
5 Correct 519 ms 8216 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
6 Correct 525 ms 8260 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
7 Correct 535 ms 8384 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
8 Correct 580 ms 8260 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
9 Correct 533 ms 8292 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
10 Correct 532 ms 8220 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1