oj.uz

Submission #969412

# Submission time Handle Problem Language Result Execution time Memory
969412 2024-04-25T06:25:34 Z vjudge1 Holiday (IOI14_holiday) C++17
7 / 100
 862 ms 65536 KB 
#include"holiday.h"
#include<bits/stdc++.h>
#define II signed
#define int long long
using namespace std;
int optL[3000],optR[3000],valL[7500],valR[7500],sums[2000][2000];
void MLE(){
    vector<int>v;
    for(;;)
        v.push_back(12);
}
int proc(II n, II &start, II d,II arr[]){
    memset(sums,0,sizeof sums);
    memset(valL,0,sizeof valL);
    memset(valR,0,sizeof valR);
    multiset<int> st;
    for(int i=start;i>-1;i--){
        st.insert(arr[i]);
        auto it=st.end();
        for(int j=1;j<=start-i+1;j++)
            it--,sums[i][j]=sums[i][j-1]+*it;
        for(int j=start-i+2;j<=d;j++)
            sums[i][j]=sums[i][j-1];
    }
    st.clear();
    for(int i=start;++i<n;){
        st.insert(arr[i]);
        auto it=st.end();
        for(int j=1;j<=i-start;j++)
            it--,sums[i][j]=sums[i][j-1]+*it;
        for(int j=i-start+1;j<=d;j++)
            sums[i][j]=sums[i][j-1];
    }
    for(int i=0;++i<=d;)
        for(int j=0;j<=start;j++)
            if(2*(start-j)<i&&valL[i]<sums[j][min((long long)n,i-2*(start-j))])
                valL[i]=sums[j][i-2*(start-j)],optL[i]=j;
    for(int i=2;i<=d;i++)
        if(optL[i]>optL[i-1])
            MLE();
    for(int i=0;++i<=d;)
        for(int j=start;j<=n;j++)
            if(j-start<i&&valR[i]<!!(j-start)*sums[j][min((long long)n,i-j+start)])
                valR[i]=sums[j][i-j+start],optR[i]=j;
    for(int i=2;i<=d;i++)
        if(optR[i]<optR[i-1])
            MLE();
    int ANS=0;
    for(int i=0;i<=d;i++)
        ANS=max(ANS,valL[i]+valR[d-i]);
    reverse(arr,arr+n);
    start=n-1-start;
    return ANS;
}
int findMaxAttraction(II n, II start, II d, II attraction[]) {
    return max(proc(n,start,d,attraction),proc(n,start,d,attraction));
}

Subtask #1
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 32344 KB Output is correct
2 Correct 7 ms 32092 KB Output is correct
3 Correct 7 ms 32072 KB Output is correct
4 Correct 8 ms 32088 KB Output is correct
5 Correct 7 ms 32092 KB Output is correct
6 Correct 7 ms 32256 KB Output is correct
7 Correct 7 ms 32092 KB Output is correct

Subtask #2
0 / 23.0

# Verdict Execution time Memory Grader output
1 Runtime error 862 ms 65496 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 17.0

# Verdict Execution time Memory Grader output
1 Runtime error 29 ms 64848 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 53.0

# Verdict Execution time Memory Grader output
1 Runtime error 41 ms 65536 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -