oj.uz

Submission #72261

# Submission time Handle Problem Language Result Execution time Memory
72261 2018-08-26T06:30:23 Z BBBSNG(#2263, youngyojun, sebinkim, dlalswp25) Gorgeous Pill (FXCUP3_gorgeous) C++14
51 / 100
 55 ms 17480 KB 
#include <bits/stdc++.h>
#define rf(x) (x)=0;while(*p<48)p++;while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);
//#define rf(x) (x)=0;while(*p<48)im=*p=='-';while(47<*p)(x)=((x)<<3)+((x)<<1)+(*p++&15);if(im)(x)=-(x);
#define pb push_back
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define befv(V) ((V)[(sz(V)-2)])
#define sorv(V) sort(allv(V))
#define revv(V) reverse(allv(V))
#define univ(V) (V).erase(unique(allv(V)),(V).end())
#define clv(V) (V).clear()
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define rb(x) ((x)&(-(x)))
#define cb(x) (x)=(!(x))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
#define INFST (0x7f7f7f7f)
#define INFLLST (0x7f7f7f7f7f7f7f7fll)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<int, ll> pil;
typedef pair<ll, int> pli;
typedef pair<ld, ld> pdd;
typedef complex<ld> base;
const ld EPS = (ld)1e-7;
const ld PI = acos(0) * 2;
bool isZero(const ld& x) { return abs(x) <= EPS; }
int sign(const ld& x) { return isZero(x) ? 0 : (0 < x ? 1 : -1); }
ll gcd(ll a, ll b) { for(;b;a%=b,swap(a,b)){} return abs(a); }
pll operator + (const pll& a, const pll& b) { return pll(a.first+b.first, a.second+b.second); }
pll operator - (const pll& a, const pll& b) { return pll(a.first-b.first, a.second-b.second); }
pll operator * (const pll& a, const ll& b) { return pll(a.first*b, a.second*b); }
ll operator * (const pll& a, const pll& b) { return a.first*b.second - b.first*a.second; }
ll ccw(const pll& a, const pll& b, const pll& c) { return a*b + b*c + c*a; }
void fg(vector<int> G[], int a, int b) { G[a].pb(b); G[b].pb(a); }
void fg(vector<pii> G[], int a, int b, int c) { G[a].pb({b, c}); G[b].pb({a, c}); }

const int MAXN = 1005;

ll dp[MAXN][MAXN];
bitset<MAXN> chk[MAXN];

int A[MAXN], B[MAXN];

int N;

ll f(int s, int e) {
	if(1 == s && e == N) return 0;
	ll &ret = dp[s][e];
	if(chk[s][e]) return ret;
	chk[s][e] = true;

	int k = e - s + 2;
	if(e < N) upmax(ret, f(s, e+1) + (A[e+1] == k ? B[e+1] : 0));
	if(1 < s) upmax(ret, f(s-1, e) + (A[s-1] == k ? B[s-1] : 0));
	return ret;
}

int main() {
	ios::sync_with_stdio(false);

	cin >> N;
	for(int i = 1; i <= N; i++) cin >> A[i];
	for(int i = 1; i <= N; i++) cin >> B[i];

	for(int i = 1; i <= N; i++)
		printf("%lld ", f(i, i) + (1 == A[i] ? B[i] : 0));
	puts("");
	return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 716 KB Output is correct
6 Correct 3 ms 760 KB Output is correct

Subtask #2
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 716 KB Output is correct
6 Correct 3 ms 760 KB Output is correct
7 Correct 3 ms 760 KB Output is correct
8 Correct 2 ms 928 KB Output is correct
9 Correct 4 ms 1056 KB Output is correct
10 Correct 6 ms 2636 KB Output is correct
11 Correct 20 ms 5844 KB Output is correct
12 Correct 22 ms 7132 KB Output is correct
13 Correct 22 ms 7644 KB Output is correct
14 Correct 27 ms 7664 KB Output is correct
15 Correct 20 ms 7664 KB Output is correct

Subtask #3
0 / 49.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 596 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 596 KB Output is correct
5 Correct 2 ms 716 KB Output is correct
6 Correct 3 ms 760 KB Output is correct
7 Correct 3 ms 760 KB Output is correct
8 Correct 2 ms 928 KB Output is correct
9 Correct 4 ms 1056 KB Output is correct
10 Correct 6 ms 2636 KB Output is correct
11 Correct 20 ms 5844 KB Output is correct
12 Correct 22 ms 7132 KB Output is correct
13 Correct 22 ms 7644 KB Output is correct
14 Correct 27 ms 7664 KB Output is correct
15 Correct 20 ms 7664 KB Output is correct
16 Runtime error 55 ms 17480 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Halted 0 ms 0 KB -