oj.uz

Submission #69655

# Submission time Handle Problem Language Result Execution time Memory
69655 2018-08-21T10:46:39 Z vanogam Homecoming (BOI18_homecoming) C++14
100 / 100
 261 ms 240768 KB 
#include<bits/stdc++.h>
#include "homecoming.h"
using namespace std;
long long a,s,d[2000002][2],f[2000002][2],g[2000002],h[2000002],j,k,l,i,n,m;
long long get(int l,int r){
    l++;r++;
    //cout<<l<<" "<<r<<" "<<g[l]<<" "<<g[r-1]<<" "<<g[n]<<endl;
    if(r>=l) return g[r]-g[l-1];
    else return (g[n]-g[l-1])+g[r];
}

int gi(int i){
    if(i>=n) i-=n;
    return i;
}
long long solve(int N,int K,int *A,int *B){
    long long s1=A[0]-B[0];
    n=N;
    k=K;
    g[1]=B[0];
    g[0]=0;
    for(i=2;i<=n;i++){
        s1+=A[i-1]-B[i-1];
        g[i]=g[i-1]+B[i-1];
    }
    if(n==k) return max(s1,0ll);
    //memset(d,~0,sizeof d);
    d[0][1]=-1000000000000000000ll;
    d[0][0]=A[0]-g[k];
    h[n-1]=A[n-1];//cout<<d[0][0]<<" "<<d[0][1]<<endl;
    for(i=n-2;i>=n-k;i--) h[i]=h[i+1]+A[i];
    d[n-1][0]=0;
    for(i=1;i<n;i++){
        if(i+k-1>=n-1) {
            if(i==n-1) d[i][0]=max(d[i][0],d[i-1][0]+A[i]-((i+k==n)*B[n-1])); else
            d[i][0]=d[i-1][0]+A[i]-((i+k==n)*B[n-1]);

            if(d[i-1][1]+A[i]-get(i,n-1)>d[i][0]){
                d[i][0]=d[i-1][1]+A[i]-get(i,n-1);
            }
            //d[n-1][0]=max(d[n-1][0],max(d[i-k-1][0],d[i-k-1][1])+h[i]-get(i,n-1));
            d[i][1]=max(d[i-1][1],d[i-1][0]);
            //cout<<d[i][0]<<" "<<d[i][1]<<endl;
            continue;
        }
        d[i][0]=d[i-1][0]+A[i]-B[gi(i+k-1)];
        if(d[i-1][1]!=-1 && d[i-1][1]+A[i]-get(i,gi(i+k-1))>d[i][0]) {
            d[i][0]=d[i-1][1]+A[i]-get(i,gi(i+k-1));
        }

        d[i][1]=max(d[i-1][1],d[i-1][0]);
    }
    f[0][0]=-1000000000000000000ll;
    f[0][1]=0;
    for(i=1;i<n;i++){
        f[i][0]=f[i-1][0]+A[i]-B[gi(i+k-1)];
        //cout<<i<<"* "<<-get(i,gi(i+k-1))<<endl;
        if(f[i-1][1]+A[i]-get(i,gi(i+k-1))>f[i][0]) {

            f[i][0]=f[i-1][1]+A[i]-get(i,gi(i+k-1));
        }

        f[i][1]=max(f[i-1][1],f[i-1][0]);//cout<<f[i][0]<<" "<<f[i][1]<<endl;
    }
    return (long long)(max(max(d[n-1][0],d[n-1][1]),max(f[n-1][0],f[n-1][1])));
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 3 ms 672 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 3 ms 672 KB Output is correct
6 Correct 3 ms 672 KB Output is correct
7 Correct 3 ms 868 KB Output is correct
8 Correct 5 ms 868 KB Output is correct
9 Correct 2 ms 868 KB Output is correct
10 Correct 4 ms 868 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 65 ms 24108 KB Output is correct
2 Correct 6 ms 24108 KB Output is correct
3 Correct 246 ms 94580 KB Output is correct
4 Correct 8 ms 94580 KB Output is correct
5 Correct 16 ms 94580 KB Output is correct

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 3 ms 504 KB Output is correct
4 Correct 2 ms 504 KB Output is correct
5 Correct 3 ms 672 KB Output is correct
6 Correct 3 ms 672 KB Output is correct
7 Correct 3 ms 868 KB Output is correct
8 Correct 5 ms 868 KB Output is correct
9 Correct 2 ms 868 KB Output is correct
10 Correct 4 ms 868 KB Output is correct
11 Correct 65 ms 24108 KB Output is correct
12 Correct 6 ms 24108 KB Output is correct
13 Correct 246 ms 94580 KB Output is correct
14 Correct 8 ms 94580 KB Output is correct
15 Correct 16 ms 94580 KB Output is correct
16 Correct 261 ms 137844 KB Output is correct
17 Correct 109 ms 137844 KB Output is correct
18 Correct 245 ms 137844 KB Output is correct
19 Correct 184 ms 171708 KB Output is correct
20 Correct 208 ms 240768 KB Output is correct
21 Correct 188 ms 240768 KB Output is correct