oj.uz

답안 #281974

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
281974 2020-08-23T18:06:36 Z Atalasion Homecoming (BOI18_homecoming) C++14
0 / 100
 99 ms 48248 KB 
#include <bits/stdc++.h>
#include "homecoming.h"

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
using namespace std;

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

const int NN = 4000000 + 10;
const int MOD = 1000000007;
const int LOG = 20;
const int INF = 1000000000000000010;
const int delta = 11353;

ll dp[NN][2], sm[NN], ps[NN];
int n, k, A[NN], B[NN];

ll solve(int N, int K, int *A, int *B){
	ps[0] = 0;
	n = N;
	for (int i = n; i < 2 * n; i++) B[i] = B[i - n];
	for (int i = 1; i <= 2 * n; i++){
		ps[i] = ps[i - 1] + B[i - 1];
	//	cout << i << ' ' << ps[i] << '\n';
	}
	if (K == n){
		ll ans = 0;
		ll Sum = 0;
		for (int i = 0; i < n; i++) Sum += A[i], Sum -= B[i];
		return max(ans, Sum);
	}
	for (int i = 0; i < n; i++)sm[i] = ps[i + 1 + K - 1] - ps[i];
//	for (int i = 0; i < n; i++) cout << i << ' ' << sm[i] << '\n';
	ll ans = 0;
	ll Sum = 0;
	for (int i = 0; i < n; i++) Sum += A[i], Sum -= B[i];
	ans = max(ans, Sum);
	for (int i = 0; i < n; i++) for (int j = 0; j < 2; j++) dp[i][j] = -INF;
	dp[n - 1][0] = 0, dp[n - 1][1] = A[n - 1] - B[n - 1];
	//cout << dp[n - 1][0] << ' ' << dp[n - 1][1] << '\n';
	for (int i = n - 2; i >= 0; i--){
		dp[i][0] = max(dp[i + 1][1], dp[i + 1][0]);
		dp[i][1] = max(dp[i + 1][0] + A[i] - sm[i], dp[i + 1][1] + A[i] - B[i]);
		//cout << i << ' ' << dp[i][0] << ' ' << dp[i][1] << '\n';
	}
	Sum = A[0] - sm[0];
	for (int i = 1; i < n; i++){
		ans = max(ans, dp[i][0] + Sum);
		Sum += sm[i - 1] - B[i - 1];
		Sum += A[i] - sm[i];
	}
	//cout << ans << '\n';
	for (int i = 0; i < n; i++) for (int j = 0; j < 2; j++) dp[i][j] = -INF;
	dp[n - 1][0] = 0, dp[n - 1][1] = A[n - 1] - sm[n - 1];
	for (int i = n - 2; i >= 0; i--){
		dp[i][0] = max(dp[i + 1][0], dp[i + 1][1]);
		dp[i][1] = max(dp[i + 1][0] + A[i] - sm[i], dp[i + 1][1] + A[i] - B[i]);
		//cout << i << ' ' << dp[i][0] << ' ' << dp[i][1] << '\n';
	}
	ans = max(ans, dp[0][0]);
	return ans;
}

Compilation message

homecoming.cpp:18:17: warning: overflow in conversion from 'long int' to 'int' changes value from '1000000000000000010' to '-1486618614' [-Woverflow]
   18 | const int INF = 1000000000000000010;
      |                 ^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Runtime error 11 ms 768 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Runtime error 11 ms 768 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 99 ms 48248 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Runtime error 11 ms 768 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -