Submission #731173

#	Time	Username	Problem	Language	Result	Execution time	Memory
731173		alexdd	Secret (JOI14_secret)	C++17	100 / 100	483 ms	8304 KiB

secret

#include "secret.h"
#include<bits/stdc++.h>
using namespace std;
/*ifstream fin("secret.in");
ofstream fout("secret.out");
int cate=0;
int Secret(int x, int y)
{
    if(!bl) cate++;
    return x+y;
}*/

bool bl=0;
int n;
int a[1005];
int prec[1005][1005];
void precalc(int st, int dr)
{
    if(st==dr)
        return;
    int mij=(st+dr)/2;
    for(int i=mij-1;i>=st;i--)
        if(prec[i][mij]==-1)
            prec[i][mij] = Secret(a[i],prec[i+1][mij]);
    for(int i=mij+2;i<=dr;i++)
        if(prec[mij+1][i]==-1)
            prec[mij+1][i] = Secret(prec[mij+1][i-1],a[i]);
    precalc(st,mij);
    precalc(mij+1,dr);
}
void Init(int N, int A[])
{
    n=N;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            prec[i][j]=-1;
    for(int i=0;i<n;i++)
    {
        a[i]=A[i];
        prec[i][i]=a[i];
    }
    bl=0;
    precalc(0,n-1);
    bl=1;
}
int Query(int L, int R)
{
    if(L==R)
        return a[L];
    if(R-L==1)
        return Secret(a[L],a[R]);
    for(int mij=L;mij<R;mij++)
        if(prec[L][mij]!=-1 && prec[mij+1][R]!=-1)
            return Secret(prec[L][mij], prec[mij+1][R]);
    return -1;
}
/*int A[1000];
signed main()
{
    for(int i=0;i<1000;i++)
        A[i]=i;
    Init(1000,A);
    fout<<cate<<"\n";
    int aux;
    for(int i=0;i<1000;i++)
    {
        for(int j=i;j<1000;j++)
        {
            aux = Query(i,j);
            if(aux!=j*(j+1)/2 - i*(i-1)/2)fout<<i<<" "<<j<<"   "<<aux<<"\n";
        }
    }
    return 0;
}*/

• Subtask 1: 100 / 100