oj.uz

Submission #80448

# Submission time Handle Problem Language Result Execution time Memory
80448 2018-10-20T18:41:23 Z igzi Homecoming (BOI18_homecoming) C++17
62 / 100
 1000 ms 141864 KB 
#include <bits/stdc++.h>
#include "homecoming.h"
#define maxN 2000005

using namespace std;

int n,k,i,a[maxN],b[maxN];
long long dp[maxN],sb[maxN],tmp[maxN],p[maxN],q[maxN];

long long dp0(int n,int k,long long a[],long long b[]){
long long i,ans=0;
deque <long long> dq;
sb[n-1]=b[n-1];
for(i=n-2;i>=0;i--) sb[i]=sb[i+1]+b[i];
dp[n-1]=a[n-1]-b[n-1];
tmp[n-1]=max((long long) 0,dp[n-1]);
ans=tmp[n-1];
dq.push_back(n-1);
for(i=n-2;i>=0;i--){
    long long x=dq.front();
    dp[i]=a[i]+dp[x]-sb[i]+sb[x];
    if(i+k<n) dp[i]=max(dp[i],tmp[i+k]+a[i]-sb[i]+sb[i+k]);
    ans=max(ans,dp[i]);
    tmp[i]=ans;
    if(dq.front()==i+k) dq.pop_front();
    while(dq.size() && dp[dq.back()]+sb[dq.back()]<=dp[i]+sb[i]){
        dq.pop_back();
    }
    dq.push_back(i);
}
return ans;
}

long long solve(int n,int k,int a[],int c[]){
long long ans=0,s;
int i,j;
for(i=0;i<n;i++) b[i]=c[i];
for(j=0;j<k;j++){
s=0;
for(i=0;i<n;i++){
    p[i]=a[(i+j)%n];
    if(i>=k) q[i]=b[(i+j)%n];
    else q[i]=0;
    if(i<k) s+=b[(i+j)%n];
    }
    ans=max(ans,dp0(n,k,p,q)-s);
}
for(i=k;i<n;i++){
    p[i-k]=a[i];
    q[i-k]=b[i];
}
for(i=n-k;i<n;i++){
    p[i]=0;
    q[i]=b[(i+k)%n];
}
ans=max(ans,dp0(n,k,p,q));
return ans;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 5 ms 508 KB Output is correct
3 Correct 2 ms 508 KB Output is correct
4 Correct 3 ms 700 KB Output is correct
5 Correct 3 ms 700 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 5 ms 508 KB Output is correct
3 Correct 2 ms 508 KB Output is correct
4 Correct 3 ms 700 KB Output is correct
5 Correct 3 ms 700 KB Output is correct
6 Correct 421 ms 760 KB Output is correct
7 Correct 311 ms 768 KB Output is correct
8 Correct 61 ms 768 KB Output is correct
9 Correct 11 ms 768 KB Output is correct
10 Correct 5 ms 768 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 90 ms 26004 KB Output is correct
2 Correct 39 ms 26004 KB Output is correct
3 Correct 241 ms 102292 KB Output is correct
4 Correct 37 ms 102292 KB Output is correct
5 Correct 53 ms 102292 KB Output is correct

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 5 ms 508 KB Output is correct
3 Correct 2 ms 508 KB Output is correct
4 Correct 3 ms 700 KB Output is correct
5 Correct 3 ms 700 KB Output is correct
6 Correct 421 ms 760 KB Output is correct
7 Correct 311 ms 768 KB Output is correct
8 Correct 61 ms 768 KB Output is correct
9 Correct 11 ms 768 KB Output is correct
10 Correct 5 ms 768 KB Output is correct
11 Correct 90 ms 26004 KB Output is correct
12 Correct 39 ms 26004 KB Output is correct
13 Correct 241 ms 102292 KB Output is correct
14 Correct 37 ms 102292 KB Output is correct
15 Correct 53 ms 102292 KB Output is correct
16 Execution timed out 1064 ms 141864 KB Time limit exceeded
17 Halted 0 ms 0 KB -