oj.uz

Submission #731173

# Submission time Handle Problem Language Result Execution time Memory
731173 2023-04-27T06:20:33 Z alexdd Secret (JOI14_secret) C++17
100 / 100
 483 ms 8304 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 129 ms 4424 KB Output is correct - number of calls to Secret by Init = 3084, maximum number of calls to Secret by Query = 1
2 Correct 128 ms 4428 KB Output is correct - number of calls to Secret by Init = 3092, maximum number of calls to Secret by Query = 1
3 Correct 122 ms 4412 KB Output is correct - number of calls to Secret by Init = 3101, maximum number of calls to Secret by Query = 1
4 Correct 439 ms 8264 KB Output is correct - number of calls to Secret by Init = 6989, maximum number of calls to Secret by Query = 1
5 Correct 437 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 457 ms 8272 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
7 Correct 483 ms 8304 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
8 Correct 443 ms 8248 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
9 Correct 443 ms 8304 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1
10 Correct 450 ms 8192 KB Output is correct - number of calls to Secret by Init = 6997, maximum number of calls to Secret by Query = 1