oj.uz

답안 #683216

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
683216 2023-01-17T23:43:54 Z theartofwar 수열 (APIO14_sequence) C++14
50 / 100
 735 ms 131072 KB 
#pragma GCC optimize("Ofast")
#pragma GCC optimization ("unroll-loops")
#include <bits/stdc++.h>
#define rsrt(v) sort(v.begin(), v.end(), greater<int>())
#define srt(v) sort(v.begin(),v.end())
#define all(x) (x).begin(),(x).end()
#define ll long long
#define int long long
ll md = 1000000007;
int inf = 1e18;
using namespace std;
template <typename T>
T pw(T a, T b) {T c = 1, m = a;while(b) {if (b & 1) c=(c*m); m=(m*m); b/=2;} return c;}
template <typename T>
T ceel(T a, T b){if (a%b==0) return a/b; else return a/b + 1;}
template <typename T>
T gcd(T a, T b) {return b == 0 ? a : gcd(b, a % b);}
ll pwmd(ll a, ll b) {ll c = 1, m = a%md;while(b) {if (b & 1) c=(c*m)%md; m=(m*m)%md; b/=2;} return c;}
ll modinv(ll n){return pwmd(n, md - 2);}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll random(ll l, ll r){ // gives random number in [l,r]
  return uniform_int_distribution<ll>(l, r)(rng);
}
template <class T1, class T2>
ostream &operator<<(ostream &os, const pair<T1, T2> &p) {
  return os << '{' << p.first << ", " << p.second << '}';
}
template <class T, class = decay_t<decltype(*begin(declval<T>()))>,
          class = enable_if_t<!is_same<T, string>::value>>
ostream &operator<<(ostream &os, const T &c) {
  os << '[';
  for (auto it = c.begin(); it != c.end(); ++it)
    os << &", "[2 * (it == c.begin())] << *it;
  return os << ']';
}
//support up to 5 args
#define _NTH_ARG(_1, _2, _3, _4, _5, _6, N, ...) N
#define _FE_0(_CALL, ...)
#define _FE_1(_CALL, x) _CALL(x)
#define _FE_2(_CALL, x, ...) _CALL(x) _FE_1(_CALL, __VA_ARGS__)
#define _FE_3(_CALL, x, ...) _CALL(x) _FE_2(_CALL, __VA_ARGS__)
#define _FE_4(_CALL, x, ...) _CALL(x) _FE_3(_CALL, __VA_ARGS__)
#define _FE_5(_CALL, x, ...) _CALL(x) _FE_4(_CALL, __VA_ARGS__)
#define FOR_EACH_MACRO(MACRO, ...)                                             \
  _NTH_ARG(dummy, ##__VA_ARGS__, _FE_5, _FE_4, _FE_3, _FE_2, _FE_1, _FE_0)     \
  (MACRO, ##__VA_ARGS__)
// #ifdef LOCAL
#define out(x) #x " = " << x << "; "
#define dbg(...)                                                              \
  cerr << "Line " << __LINE__ << ": " FOR_EACH_MACRO(out, __VA_ARGS__) << "\n"
// #else
// #define debug(...) 42
// #endif
//--------------------------------theartofwar-------------------------------------------//
// This is for maximum query, for minimum query you can make slope and intercept -ve
struct Line {
	mutable ll k, m, p;
	bool operator<(const Line& o) const { return k < o.k; }
	bool operator<(ll x) const { return p < x; }
};
struct LineContainer : multiset<Line, less<>> {
	// (for doubles, use inf = 1/.0, div(a,b) = a/b)
	static const ll inf = LLONG_MAX;
	ll div(ll a, ll b) { // floored division
		return a / b - ((a ^ b) < 0 && a % b); }
	bool isect(iterator x, iterator y) {
		if (y == end()) return x->p = inf, 0;
		if (x->k == y->k) x->p = x->m > y->m ? inf : -inf;
		else x->p = div(y->m - x->m, x->k - y->k);
		return x->p >= y->p;
	}
	void add(ll k, ll m) { // k = slope, m = intercept
		auto z = insert({k, m, 0}), y = z++, x = y;
		while (isect(y, z)) z = erase(z);
		if (x != begin() && isect(--x, y)) isect(x, y = erase(y));
		while ((y = x) != begin() && (--x)->p >= y->p)
			isect(x, erase(y));
	}
	pair<int, int> query(ll x) {
		assert(!empty());
		auto l = *lower_bound(x);
		return {l.k,  l.m};
	}
};
signed main()
{
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int n, k;
	cin >> n >> k;
	vector<int> v(n);
	for (int i = 0; i < n; i++) cin >> v[i];
	vector<LineContainer> vlc;
	for (int i = 0; i <= k + 1; i++) {
		LineContainer tmp;
		vlc.push_back(tmp);
	}
	vector<vector<int>> dp(n, vector<int>(k + 2)), rev(n, vector<int>(k + 2, -1));
	map<pair<int, int>, int> pos[k + 2];
	int pre = 0;
	for (int i = 0; i < n; i++) {
		pre += v[i];
		for (int j = k + 1; j >= 2; j--) {
			if (j > i + 1) continue;
			int a, b;
			auto p = vlc[j - 1].query(pre);
			a = p.first, b = p.second;
			rev[i][j] = pos[j - 1][p];
			int a0 = a * pre + b;
			dp[i][j] = a0;
			pos[j][{pre, a0 - pre * pre}] = i;
			vlc[j].add(pre, a0 - pre * pre);
		}
		vlc[1].add(pre, 0 - pre * pre);
		pos[1][{pre, 0 - pre * pre}] = i;
	}
	cout << dp[n - 1][k + 1] << "\n";
	vector<int> seq;
	int e = k + 1, f = n - 1;
	while (e > 1) {
		f = rev[f][e], e--;
		seq.push_back(f);
	}
	srt(seq);
	for (auto s : seq) cout << (s + 1) << " ";
}


/* 

1,1,1,1,1,1

a, b, c, d, e, f

(a, b) (c, d) (e, f)

(a + b)(c + d + e + f) + (c + d)(e + f) = (a + b)(c + d) + (a + b)(e + f) + (c + d)(e + f)

(e + f)(a + b + c + d)  + (a + b)(c + d)

(a + b)(c + d) + (a + b)(e + f) + (c + d)(e + f)

(x - s0) * s0 + a0

s0 * x + a0 - s0 * s0

a, b, c, d

ab + c(a + b) + d(a + b + c)
a(b + c) + b(c + d) + d(a + b)
4, 4, 4, 5
16 + 32 + 60 = 108


8 4 5
32 + 



 */

Compilation message

sequence.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization ("unroll-loops")
      |

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB contestant found the optimal answer: 108 == 108
2 Correct 0 ms 212 KB contestant found the optimal answer: 999 == 999
3 Correct 0 ms 212 KB contestant found the optimal answer: 0 == 0
4 Correct 1 ms 212 KB contestant found the optimal answer: 1542524 == 1542524
5 Correct 0 ms 212 KB contestant found the optimal answer: 4500000000 == 4500000000
6 Correct 0 ms 212 KB contestant found the optimal answer: 1 == 1
7 Correct 0 ms 212 KB contestant found the optimal answer: 1 == 1
8 Correct 0 ms 212 KB contestant found the optimal answer: 1 == 1
9 Correct 1 ms 212 KB contestant found the optimal answer: 100400096 == 100400096
10 Correct 0 ms 212 KB contestant found the optimal answer: 900320000 == 900320000
11 Correct 0 ms 212 KB contestant found the optimal answer: 3698080248 == 3698080248
12 Correct 0 ms 212 KB contestant found the optimal answer: 3200320000 == 3200320000
13 Correct 0 ms 212 KB contestant found the optimal answer: 140072 == 140072
14 Correct 0 ms 296 KB contestant found the optimal answer: 376041456 == 376041456
15 Correct 0 ms 212 KB contestant found the optimal answer: 805 == 805
16 Correct 0 ms 212 KB contestant found the optimal answer: 900189994 == 900189994
17 Correct 0 ms 212 KB contestant found the optimal answer: 999919994 == 999919994

Subtask #2
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 340 KB contestant found the optimal answer: 1093956 == 1093956
2 Correct 0 ms 340 KB contestant found the optimal answer: 302460000 == 302460000
3 Correct 1 ms 468 KB contestant found the optimal answer: 122453454361 == 122453454361
4 Correct 1 ms 340 KB contestant found the optimal answer: 93663683509 == 93663683509
5 Correct 1 ms 340 KB contestant found the optimal answer: 1005304678 == 1005304678
6 Correct 1 ms 340 KB contestant found the optimal answer: 933702 == 933702
7 Correct 1 ms 468 KB contestant found the optimal answer: 25082842857 == 25082842857
8 Correct 1 ms 340 KB contestant found the optimal answer: 687136 == 687136
9 Correct 1 ms 340 KB contestant found the optimal answer: 27295930079 == 27295930079
10 Correct 1 ms 340 KB contestant found the optimal answer: 29000419931 == 29000419931

Subtask #3
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB contestant found the optimal answer: 610590000 == 610590000
2 Correct 1 ms 340 KB contestant found the optimal answer: 311760000 == 311760000
3 Correct 9 ms 3416 KB contestant found the optimal answer: 1989216017013 == 1989216017013
4 Correct 1 ms 340 KB contestant found the optimal answer: 1499437552673 == 1499437552673
5 Correct 7 ms 2612 KB contestant found the optimal answer: 1019625819 == 1019625819
6 Correct 9 ms 2736 KB contestant found the optimal answer: 107630884 == 107630884
7 Correct 12 ms 3412 KB contestant found the optimal answer: 475357671774 == 475357671774
8 Correct 3 ms 1492 KB contestant found the optimal answer: 193556962 == 193556962
9 Correct 3 ms 1024 KB contestant found the optimal answer: 482389919803 == 482389919803
10 Correct 4 ms 1492 KB contestant found the optimal answer: 490686959791 == 490686959791

Subtask #4
17.0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 852 KB contestant found the optimal answer: 21503404 == 21503404
2 Correct 2 ms 852 KB contestant found the optimal answer: 140412195 == 140412195
3 Correct 173 ms 26040 KB contestant found the optimal answer: 49729674225461 == 49729674225461
4 Correct 2 ms 852 KB contestant found the optimal answer: 37485571387523 == 37485571387523
5 Correct 136 ms 20648 KB contestant found the optimal answer: 679388326 == 679388326
6 Correct 120 ms 17604 KB contestant found the optimal answer: 4699030287 == 4699030287
7 Correct 177 ms 25644 KB contestant found the optimal answer: 12418819758185 == 12418819758185
8 Correct 156 ms 25980 KB contestant found the optimal answer: 31093317350 == 31093317350
9 Correct 21 ms 5460 KB contestant found the optimal answer: 12194625429236 == 12194625429236
10 Correct 56 ms 10168 KB contestant found the optimal answer: 12345131038664 == 12345131038664

Subtask #5
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 21 ms 5716 KB contestant found the optimal answer: 1818678304 == 1818678304
2 Correct 20 ms 5332 KB contestant found the optimal answer: 1326260195 == 1326260195
3 Runtime error 735 ms 131072 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 337 ms 54536 KB contestant found the optimal answer: 19795776960 == 19795776960
2 Correct 322 ms 54196 KB contestant found the optimal answer: 19874432173 == 19874432173
3 Runtime error 62 ms 131072 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -