oj.uz

Submission #861504

# Submission time Handle Problem Language Result Execution time Memory
861504 2023-10-16T11:34:43 Z iskhakkutbilim Homecoming (BOI18_homecoming) C++17
0 / 100
 61 ms 40208 KB 

#ifndef EVAL
#include "homecoming.h"
#endif
#include <bits/stdc++.h>
using namespace std;
#define ll long long

const int inf = 1e17;


ll solve(int n, int k, int a[], int b[]){
	vector< vector<ll> > dp(n, vector<ll>(2, -inf));
	vector<ll> pref(n);
	pref[0] = b[0];
	for(int i = 1;i < n; i++){
		pref[i] = pref[i-1] + b[i];
	}	
	ll ans = 0; 
	dp[0][1] = a[0] - pref[k-1];
	for(int i = 1;i < n; i++){
		dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
		dp[i][1] = max(dp[i-1][0] + a[i] - pref[min(n-1, i + k-1)] - pref[i-1], 
				   dp[i-1][1] + a[i] - (i + k-1 < n ? b[i+k-1] : 0LL));
	}
	ans = max(ans, dp[n-1][0]);
	ans = max(ans, dp[n-1][1]);
	for(int i = 0;i < n; i++) dp[i][0] = dp[i][1] = -inf;
	dp[0][0] = 0;
	for(int i = 1;i < n; i++){
		dp[i][0] = max(dp[i-1][0], dp[i-1][1]);
		dp[i-1][1] = max(dp[i-1][0] + a[i] + pref[min(n, i + k-1)] - pref[i-1] + (i + k-1 >= n ? pref[i+k-1-n] : 0LL), 
					dp[i-1][1] + a[i] - b[(i + k-1) % n]);
	}
	
	
	ans = max(ans, dp[n-1][0]);
	ans = max(ans, dp[n-1][1]);
	cout << ans;
}

Compilation message

homecoming.cpp:10:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+17' to '2147483647' [-Woverflow]
   10 | const int inf = 1e17;
      |                 ^~~~
homecoming.cpp: In function 'long long int solve(int, int, int*, int*)':
homecoming.cpp:41:1: warning: no return statement in function returning non-void [-Wreturn-type]
   41 | }
      | ^

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 61 ms 40208 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 604 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -