oj.uz

Submission #68925

# Submission time Handle Problem Language Result Execution time Memory
68925 2018-08-19T09:17:22 Z istlemin Homecoming (BOI18_homecoming) C++14
62 / 100
 1000 ms 184524 KB 
#include<bits/stdc++.h>
#include "homecoming.h"

using namespace std;

#define rep(i,a,b) for(int i = a; i<int(b);++i)
#define all(v) v.begin(),v.end()
#define sz(v) v.size()
#define trav(a,c) for(auto a: c)

typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pii;

ll n,k;
vi a,b;
vi sumB;
ll start;

ll getSum(ll l,ll r){
	if(r<l) return 0;
    return sumB[r]-sumB[l];
}

ll getCost(ll l,ll r){
	if(l>=n) return getCost(l-n,r-n);
    if(r>n) return getCost(l,n)+getCost(0,r-n);
    if(l<start) return getSum(start,r);
    return getSum(l,r);
}

long long solve(int N, int K, int *A, int *B){
	n = N; k = K;
	a.resize(n);
	b.resize(n);
	rep(i,0,n) a[i] = A[i];
	rep(i,0,n) b[i] = B[i];
    sumB.resize(n+1);
    rep(i,1,n+1) sumB[i] = sumB[i-1]+b[i-1];

    ll best = 0;

    rep(_start,0,k+1){
        start = _start;
        ll curr = -getSum(0,start);

        vi dpFilled(n+k+1);
        vi dpEmpty(n+k+1);

        for(int i = n-1;i>=0;i--){
            ll cost = getCost(i+k-1,i+k);
            dpFilled[i] = max(dpFilled[i],a[i]-cost+dpFilled[i+1]);
            dpFilled[i] = max(dpFilled[i],dpEmpty[i+k]);

            cost = getCost(i,i+k);
            dpEmpty[i] = max(dpEmpty[i],a[i]-cost+dpFilled[i+1]);
            dpEmpty[i] = max(dpEmpty[i],dpEmpty[i+1]);
        }

        curr += dpEmpty[0];
		//cout<<start<<": "<<curr<<endl;
        best = max(best,curr);
    }

    return best;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 7 ms 488 KB Output is correct
3 Correct 2 ms 560 KB Output is correct
4 Correct 3 ms 560 KB Output is correct
5 Correct 3 ms 560 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 7 ms 488 KB Output is correct
3 Correct 2 ms 560 KB Output is correct
4 Correct 3 ms 560 KB Output is correct
5 Correct 3 ms 560 KB Output is correct
6 Correct 733 ms 1116 KB Output is correct
7 Correct 474 ms 1424 KB Output is correct
8 Correct 74 ms 1424 KB Output is correct
9 Correct 10 ms 1424 KB Output is correct
10 Correct 6 ms 1424 KB Output is correct

Subtask #3
31.0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 120 ms 24720 KB Output is correct
2 Correct 30 ms 24720 KB Output is correct
3 Correct 351 ms 134768 KB Output is correct
4 Correct 44 ms 134768 KB Output is correct
5 Correct 48 ms 134768 KB Output is correct

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 7 ms 488 KB Output is correct
3 Correct 2 ms 560 KB Output is correct
4 Correct 3 ms 560 KB Output is correct
5 Correct 3 ms 560 KB Output is correct
6 Correct 733 ms 1116 KB Output is correct
7 Correct 474 ms 1424 KB Output is correct
8 Correct 74 ms 1424 KB Output is correct
9 Correct 10 ms 1424 KB Output is correct
10 Correct 6 ms 1424 KB Output is correct
11 Correct 120 ms 24720 KB Output is correct
12 Correct 30 ms 24720 KB Output is correct
13 Correct 351 ms 134768 KB Output is correct
14 Correct 44 ms 134768 KB Output is correct
15 Correct 48 ms 134768 KB Output is correct
16 Execution timed out 1060 ms 184524 KB Time limit exceeded
17 Halted 0 ms 0 KB -