oj.uz

Submission #490871

# Submission time Handle Problem Language Result Execution time Memory
490871 2021-11-29T14:54:16 Z hohohaha Split the sequence (APIO14_sequence) C++14
100 / 100
 956 ms 89436 KB 
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,fma")
// #pragma GCC optimize("unroll-loops")

#include "bits/stdc++.h"
// #include <ext/pb_ds/assoc_container.hpp>
// #include <ext/pb_ds/trie_policy.hpp>
// #include <ext/rope>

using namespace std;
// using namespace __gnu_pbds;
// using namespace __gnu_cxx;

#define li long long
#define ld long double
#define ii pair<int, int>
#define vi vector<int> 
#define vvi vector<vi>


#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define pf push_front
#define eb emplace_back
#define em emplace
#define ob pop_back
#define om pop
#define of pop_front

#define fr front
#define bc back

#define fori(i, a, b) for(int i = (int) (a); i <= (int) (b); ++i)
#define ford(i, a, b) for(int i = (int) (a); i >= (int) (b); --i)

#define all(x) begin(x), end(x)
#define sz(x) ((int)(x).size())
#define bitc __builtin_popcountll

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand rng
#define endl '\n'
#define sp ' '

#define fastio() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

void solve();

signed main() {
// freopen("input.inp","r",stdin);
// freopen("output.out","w",stdout);
//   fastio();
   int tc = 1;
   fori(test, 1, tc) {
      solve();
   }
   return 0;
}

#define int long long
const ld pi = 4 * atan(1.0), eps = 1e-9;

const int inf = LLONG_MAX / 2ll;
const int maxn = 2e5 + 5; 
int n, k; 
int32_t arr[maxn]; 
int pref[maxn]; 

vi now, prv; 

struct line { 
	int32_t a; int b; int32_t id; 
	line(int a = 0, int b = 0, int id = 0) : a(a), b(b), id(id) {
	}
	int get(int x) { 
		return 1ll * a * x + b; 
	}
}; 

bool red(line x, line y, line z) { 
	return (x.b - y.b) * (z.a - y.a) >= (y.b - z.b) * (y.a - x.a); 
}

int32_t tr[maxn][205]; 

void solve() {
	cin >> n >> k; k++; 
	fori(i, 1, n) { 
		cin >> arr[i]; 
		pref[i] = arr[i] + pref[i - 1]; 
	}
	now = prv = vi(n + 1, -inf); 
	now[0] = 0; 
	fori(t, 1, k) { 
		now.swap(prv); 
		fill(all(now), -inf); 
//		now[0] = 0; 
		
//		cout << t << endl;
		
		vector<line> C; int ptr = -1; 
		fori(i, 1, n) { 
			if(prv[i - 1] > -inf) {
				line nw(pref[i - 1], prv[i - 1] - pref[i -1] * pref[i - 1], i - 1); 
				while(1) { 
					if(C.size() > 0 and (end(C) - 1)->a == nw.a and (end(C) - 1)->b < nw.b) C.ob(); 
					else if(C.size() > 1 and red(*(end(C) - 2), *(end(C) - 1), nw) ) C.ob(); 
					else break; 
				}
				ptr = min(ptr, (int)C.size() - 1); 
				C.eb(nw); 
			}
//			cout << i << endl;
			ptr = min(ptr, (int)C.size() - 1); 
			while(ptr + 1 < C.size() and (ptr == -1 or C[ptr].get(pref[i]) <= C[ptr + 1].get(pref[i]))) ++ptr; 
			if(ptr > -1) {
				now[i] = C[ptr].get(pref[i]); 
				tr[i][t] = C[ptr].id; 
			}
//			cout << i << sp << t << sp << ptr << sp << tr[i][t] << sp << now[i] << endl;
		}
	}
	cout << now[n] << endl; 
	int pos = n; 
	vi ans; 
	ford(i, k, 1) { 
		ans.eb(pos); //cout << pos << sp; 
//		cout << k << sp << pos << endl;
		pos = tr[pos][i]; 
	}
	reverse(all(ans)); 
	fori(i, 0, k - 2) cout << ans[i] << sp; 
}

Compilation message

sequence.cpp: In function 'void solve()':
sequence.cpp:117:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<line>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  117 |    while(ptr + 1 < C.size() and (ptr == -1 or C[ptr].get(pref[i]) <= C[ptr + 1].get(pref[i]))) ++ptr;
      |          ~~~~~~~~^~~~~~~~~~

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB contestant found the optimal answer: 108 == 108
2 Correct 0 ms 204 KB contestant found the optimal answer: 999 == 999
3 Correct 0 ms 204 KB contestant found the optimal answer: 0 == 0
4 Correct 0 ms 204 KB contestant found the optimal answer: 1542524 == 1542524
5 Correct 0 ms 204 KB contestant found the optimal answer: 4500000000 == 4500000000
6 Correct 0 ms 204 KB contestant found the optimal answer: 1 == 1
7 Correct 0 ms 204 KB contestant found the optimal answer: 1 == 1
8 Correct 0 ms 204 KB contestant found the optimal answer: 1 == 1
9 Correct 0 ms 204 KB contestant found the optimal answer: 100400096 == 100400096
10 Correct 1 ms 204 KB contestant found the optimal answer: 900320000 == 900320000
11 Correct 0 ms 204 KB contestant found the optimal answer: 3698080248 == 3698080248
12 Correct 0 ms 204 KB contestant found the optimal answer: 3200320000 == 3200320000
13 Correct 0 ms 204 KB contestant found the optimal answer: 140072 == 140072
14 Correct 0 ms 204 KB contestant found the optimal answer: 376041456 == 376041456
15 Correct 0 ms 204 KB contestant found the optimal answer: 805 == 805
16 Correct 0 ms 204 KB contestant found the optimal answer: 900189994 == 900189994
17 Correct 0 ms 204 KB contestant found the optimal answer: 999919994 == 999919994

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB contestant found the optimal answer: 1093956 == 1093956
2 Correct 0 ms 332 KB contestant found the optimal answer: 302460000 == 302460000
3 Correct 0 ms 332 KB contestant found the optimal answer: 122453454361 == 122453454361
4 Correct 0 ms 332 KB contestant found the optimal answer: 93663683509 == 93663683509
5 Correct 1 ms 332 KB contestant found the optimal answer: 1005304678 == 1005304678
6 Correct 0 ms 332 KB contestant found the optimal answer: 933702 == 933702
7 Correct 1 ms 332 KB contestant found the optimal answer: 25082842857 == 25082842857
8 Correct 0 ms 332 KB contestant found the optimal answer: 687136 == 687136
9 Correct 0 ms 332 KB contestant found the optimal answer: 27295930079 == 27295930079
10 Correct 1 ms 332 KB contestant found the optimal answer: 29000419931 == 29000419931

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 460 KB contestant found the optimal answer: 610590000 == 610590000
2 Correct 0 ms 460 KB contestant found the optimal answer: 311760000 == 311760000
3 Correct 1 ms 460 KB contestant found the optimal answer: 1989216017013 == 1989216017013
4 Correct 0 ms 460 KB contestant found the optimal answer: 1499437552673 == 1499437552673
5 Correct 1 ms 460 KB contestant found the optimal answer: 1019625819 == 1019625819
6 Correct 2 ms 460 KB contestant found the optimal answer: 107630884 == 107630884
7 Correct 1 ms 460 KB contestant found the optimal answer: 475357671774 == 475357671774
8 Correct 1 ms 460 KB contestant found the optimal answer: 193556962 == 193556962
9 Correct 1 ms 512 KB contestant found the optimal answer: 482389919803 == 482389919803
10 Correct 1 ms 460 KB contestant found the optimal answer: 490686959791 == 490686959791

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1100 KB contestant found the optimal answer: 21503404 == 21503404
2 Correct 1 ms 1100 KB contestant found the optimal answer: 140412195 == 140412195
3 Correct 4 ms 1100 KB contestant found the optimal answer: 49729674225461 == 49729674225461
4 Correct 1 ms 1100 KB contestant found the optimal answer: 37485571387523 == 37485571387523
5 Correct 5 ms 1100 KB contestant found the optimal answer: 679388326 == 679388326
6 Correct 4 ms 1100 KB contestant found the optimal answer: 4699030287 == 4699030287
7 Correct 5 ms 1100 KB contestant found the optimal answer: 12418819758185 == 12418819758185
8 Correct 4 ms 1100 KB contestant found the optimal answer: 31093317350 == 31093317350
9 Correct 2 ms 1100 KB contestant found the optimal answer: 12194625429236 == 12194625429236
10 Correct 2 ms 1100 KB contestant found the optimal answer: 12345131038664 == 12345131038664

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 8916 KB contestant found the optimal answer: 1818678304 == 1818678304
2 Correct 7 ms 8908 KB contestant found the optimal answer: 1326260195 == 1326260195
3 Correct 67 ms 9476 KB contestant found the optimal answer: 4973126687469639 == 4973126687469639
4 Correct 6 ms 9196 KB contestant found the optimal answer: 3748491676694116 == 3748491676694116
5 Correct 42 ms 8980 KB contestant found the optimal answer: 1085432199 == 1085432199
6 Correct 43 ms 8932 KB contestant found the optimal answer: 514790755404 == 514790755404
7 Correct 65 ms 9224 KB contestant found the optimal answer: 1256105310476641 == 1256105310476641
8 Correct 45 ms 9216 KB contestant found the optimal answer: 3099592898816 == 3099592898816
9 Correct 68 ms 9468 KB contestant found the optimal answer: 1241131419367412 == 1241131419367412
10 Correct 64 ms 9208 KB contestant found the optimal answer: 1243084101967798 == 1243084101967798

Subtask #6
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 88344 KB contestant found the optimal answer: 19795776960 == 19795776960
2 Correct 66 ms 88340 KB contestant found the optimal answer: 19874432173 == 19874432173
3 Correct 956 ms 89324 KB contestant found the optimal answer: 497313449256899208 == 497313449256899208
4 Correct 67 ms 89204 KB contestant found the optimal answer: 374850090734572421 == 374850090734572421
5 Correct 950 ms 88444 KB contestant found the optimal answer: 36183271951 == 36183271951
6 Correct 447 ms 86584 KB contestant found the optimal answer: 51629847150471 == 51629847150471
7 Correct 735 ms 89436 KB contestant found the optimal answer: 124074747024496432 == 124074747024496432
8 Correct 565 ms 89112 KB contestant found the optimal answer: 309959349080800 == 309959349080800
9 Correct 640 ms 89108 KB contestant found the optimal answer: 124113525649823701 == 124113525649823701
10 Correct 806 ms 88896 KB contestant found the optimal answer: 124309619349406845 == 124309619349406845