# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
969411 |
2024-04-25T06:24:50 Z |
vjudge1 |
Holiday (IOI14_holiday) |
C++17 |
|
22 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[3000][3000];
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));
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
14 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
20 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
13 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
22 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |