oj.uz

Submission #129767

# Submission time Handle Problem Language Result Execution time Memory
129767 2019-07-13T07:39:47 Z 윤교준(#3140) 도장 모으기 (JOI14_stamps) C++14
100 / 100
 788 ms 72356 KB 
#include <bits/stdc++.h>
#define eb emplace_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
#define sorv(V) sort(allv(V))
#define upmin(a,b) (a)=min((a),(b))
#define upmax(a,b) (a)=max((a),(b))
#define INF (0x3f3f3f3f)
#define INFLL (0x3f3f3f3f3f3f3f3fll)
using namespace std;
typedef long long ll;
typedef __int128_t lll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
lll operator * (const pll &a, const pll &b) { return lll(a.first)*b.second - lll(b.first)*a.second; }
lll ccw(const pll &a, const pll &b, const pll &c) { return a*b + b*c + c*a; }

const int MAXN = 3055;

struct CHT {
	pll P[MAXN];
	int n;

	void init() { n = 0; }
	void push(const pll &p) {
		for(; 1 < n && ccw(P[n-2], P[n-1], p) <= 0; n--);
		P[n++] = p;
	}
	ll f(int i, ll X) { return P[i].first*X + P[i].second; }
	ll get(ll X) {
		if(!n) return INFLL;
		ll ret = INFLL;
		int s = 0, e = n-1; for(int m; s < e;) {
			m = (s+e) >> 1;
			ll tl = f(m, X), tr = f(m+1, X);
			if(tr < tl) {
				if(tr < ret) ret = tr;
				s = m+1;
			} else {
				if(tl < ret) ret = tl;
				e = m-1;
			}
		}
		return min(ret, f(s, X));
	}
} cht;

ll dp[MAXN][MAXN];

int A[MAXN], B[MAXN], C[MAXN], D[MAXN];

int N, T;

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

	cin >> N >> T;
	for(int i = 1; i <= N; i++)
		cin >> A[i] >> B[i] >> C[i] >> D[i];
	
	fill(dp[0], dp[N+2]+(N+2), INFLL);
	dp[0][0] = 0;

	for(int i = 1; i <= N; i++) {
		cht.init();
		for(int j = 0, t; j <= N; j++) {
			t = j-1;
			if(0 <= t) cht.push({t, dp[i-1][t] + ll(2*t+1)*T});
			upmin(dp[i][j], cht.get(-B[i]-C[i]) + ll(B[i]+C[i])*j);
		}
		if(1 < i) {
		cht.init();
		for(int j = N, t; 0 <= j; j--) {
			t = j+1;
			if(t <= N) cht.push({-t, dp[i-1][t] + ll(2*t+1)*T});
			upmin(dp[i][j], cht.get(-A[i]-D[i]) - ll(A[i]+D[i])*j);
		}
		}
		for(int j = 0; j <= N; j++) {
			ll &ret = dp[i][j];
			upmin(ret, dp[i-1][j] + A[i] + B[i] + ll(j*2+1)*T);
			if(1 < i && j) upmin(ret, dp[i-1][j] + C[i] + D[i] + ll(j*2+1)*T);
		}
	}
	
	cout << dp[N][0] + T << endl;
	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 632 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 3 ms 760 KB Output is correct
5 Correct 2 ms 888 KB Output is correct
6 Correct 2 ms 760 KB Output is correct
7 Correct 2 ms 764 KB Output is correct
8 Correct 2 ms 760 KB Output is correct
9 Correct 2 ms 888 KB Output is correct
10 Correct 2 ms 888 KB Output is correct
11 Correct 2 ms 888 KB Output is correct
12 Correct 2 ms 760 KB Output is correct
13 Correct 2 ms 760 KB Output is correct

Subtask #2
75.0 / 75.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 5 ms 2808 KB Output is correct
4 Correct 2 ms 632 KB Output is correct
5 Correct 3 ms 1144 KB Output is correct
6 Correct 3 ms 1784 KB Output is correct
7 Correct 4 ms 2552 KB Output is correct
8 Correct 4 ms 2780 KB Output is correct
9 Correct 4 ms 2812 KB Output is correct
10 Correct 4 ms 2808 KB Output is correct
11 Correct 4 ms 2812 KB Output is correct
12 Correct 4 ms 2808 KB Output is correct
13 Correct 5 ms 2808 KB Output is correct
14 Correct 5 ms 2808 KB Output is correct
15 Correct 5 ms 2808 KB Output is correct
16 Correct 5 ms 2808 KB Output is correct

Subtask #3
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 475 ms 72208 KB Output is correct
2 Correct 2 ms 504 KB Output is correct
3 Correct 521 ms 72312 KB Output is correct
4 Correct 381 ms 63736 KB Output is correct
5 Correct 311 ms 56056 KB Output is correct
6 Correct 187 ms 36604 KB Output is correct
7 Correct 104 ms 27868 KB Output is correct
8 Correct 479 ms 72312 KB Output is correct
9 Correct 645 ms 72312 KB Output is correct
10 Correct 477 ms 72312 KB Output is correct
11 Correct 546 ms 72292 KB Output is correct
12 Correct 673 ms 72312 KB Output is correct
13 Correct 612 ms 72356 KB Output is correct
14 Correct 480 ms 72288 KB Output is correct
15 Correct 788 ms 72288 KB Output is correct
16 Correct 786 ms 72184 KB Output is correct
17 Correct 785 ms 72312 KB Output is correct