oj.uz

Submission #69585

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

int gi(int i){
    if(i>=n) i-=n;
    return i;
}
long long solve(int N,int K,int *A,int *B){
    n=N;
    k=K;
    g[1]=B[0];
    g[0]=0;
    for(i=2;i<=n;i++){
        g[i]=g[i-1]+B[i-1];
    }
    //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];
    for(i=1;i<n;i++){
        if(i+k-1>=n-1) {
            d[i][0]=d[i-1][0]+A[i];
            if(i+k-1==n-1) d[i][0]-=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[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 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 3 ms 560 KB Output is correct
4 Correct 3 ms 624 KB Output is correct
5 Correct 2 ms 688 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 3 ms 560 KB Output is correct
4 Correct 3 ms 624 KB Output is correct
5 Correct 2 ms 688 KB Output is correct
6 Correct 3 ms 1084 KB Output is correct
7 Correct 3 ms 1120 KB Output is correct
8 Correct 3 ms 1120 KB Output is correct
9 Incorrect 3 ms 1408 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 56 ms 24704 KB Output is correct
2 Correct 5 ms 24704 KB Output is correct
3 Incorrect 206 ms 87248 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 484 KB Output is correct
3 Correct 3 ms 560 KB Output is correct
4 Correct 3 ms 624 KB Output is correct
5 Correct 2 ms 688 KB Output is correct
6 Correct 3 ms 1084 KB Output is correct
7 Correct 3 ms 1120 KB Output is correct
8 Correct 3 ms 1120 KB Output is correct
9 Incorrect 3 ms 1408 KB Output isn't correct
10 Halted 0 ms 0 KB -