Submission #475041

#	Time	Username	Problem	Language	Result	Execution time	Memory
475041		nicolaalexandra	Secret (JOI14_secret)	C++14	100 / 100	580 ms	8384 KiB

secret

#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 (stderr)

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 / 100