oj.uz

Submission #364757

# Submission time Handle Problem Language Result Execution time Memory
364757 2021-02-09T22:11:54 Z ACmachine Split the sequence (APIO14_sequence) C++17
100 / 100
 1032 ms 85348 KB 
#include <bits/stdc++.h>
using namespace std;

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename U> using ordered_map = tree<T, U, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;
typedef double db;
typedef string str;

typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;
typedef vector<str> vstr;

#define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
#define FORD(i,j,k,in) for(int i=(j); i >=(k);i-=in)
#define REP(i,b) FOR(i,0,b,1)
#define REPD(i,b) FORD(i,b,0,1)
#define pb push_back 
#define mp make_pair
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define rsz resize 
#define MANY_TESTS int tcase; cin >> tcase; while(tcase--)
	
const double EPS = 1e-9;
const int MOD = 1e9+7; // 998244353;
const ll INFF = 1e15;
const int INF = 1e9;
const ld PI = acos((ld)-1);
const vi dy = {1, 0, -1, 0, -1, 1, 1, -1};
const vi dx = {0, 1, 0, -1, -1, 1, -1, 1};

#ifdef DEBUG
#define DBG if(1)
#else
#define DBG if(0)
#endif

#define dbg(x) cout << "(" << #x << " : " << x << ")" << endl;
// ostreams
template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "[" << par.first << ";" << par.second << "]"; return out;}
template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template<class T>
ostream& operator<<(ostream& out, const vector<T> &v){ out << "[";  REP(i, v.size()) out << v[i] << ", ";  out << "]"; return out;}
// istreams
template<class T>
istream& operator>>(istream& in, vector<T> &v){ for(auto &x : v) in >> x; return in; }
template<class T, class U>
istream& operator>>(istream& in, pair<T, U> &p){ in >> p.ff >> p.ss; return in; }
//searches
template<typename T, typename U>
T bsl(T lo, T hi, U f){ hi++; T mid; while(lo < hi){ mid = (lo + hi)/2; f(mid) ? hi = mid : lo = mid+1; } return lo; }
template<typename U>
double bsld(double lo, double hi, U f, double p = 1e-9){ int r = 3 + (int)log2((hi - lo)/p); double mid; while(r--){ mid = (lo + hi)/2; f(mid) ? hi = mid : lo = mid; } return (lo + hi)/2; }
template<typename T, typename U>
T bsh(T lo, T hi, U f){ lo--; T mid; while(lo < hi){ mid = (lo + hi + 1)/2; f(mid) ? lo = mid : hi = mid-1; } return lo; }
template<typename U>
double bshd(double lo, double hi, U f, double p = 1e-9){ int r = 3+(int)log2((hi - lo)/p); double mid; while(r--){ mid = (lo + hi)/2; f(mid) ? lo = mid : hi = mid; } return (lo + hi)/2; }
// some more utility functions
template<typename T>
pair<T, int> get_min(vector<T> &v){ typename vector<T> :: iterator it = min_element(v.begin(), v.end()); return mp(*it, it - v.begin());}
template<typename T>
pair<T, int> get_max(vector<T> &v){ typename vector<T> :: iterator it = max_element(v.begin(), v.end()); return mp(*it, it - v.begin());}        
template<typename T> bool ckmin(T& a, const T& b){return b < a ? a = b , true : false;}
template<typename T> bool ckmax(T& a, const T& b){return b > a ? a = b, true : false;}
struct line{
    ll m, c, in;
    long double intersectX(line oth){
        return (long double)(oth.c - c)/(m - oth.m);
    }
    ll eval(ll x){
        return m * x + c;
    }
};
struct hull_trick{
    deque<line> dq;
    void insert(line x){
        while((dq.size() > 0 && dq.front().m == x.m && dq.front().c <= x.c) || (dq.size() > 1 && (dq.front().intersectX(dq[1]) <= x.intersectX(dq.front()))))
            dq.pop_front();
        dq.push_front(x);
    } 
    pll query(ll p){
        while(dq.size() > 1 && dq.back().eval(p) <= dq[(int)dq.size() - 2].eval(p)) 
            dq.pop_back();
        return mp(dq.back().eval(p), dq.back().in);
    }
};
int main(){
 	ios_base::sync_with_stdio(false);
 	cin.tie(NULL); cout.tie(NULL);
	int n, k;
    cin >> n >> k;
    vi a(n); cin >> a;
	vector<ll> ps(n + 1, 0);
    REP(i, n){
        ps[i + 1] = ps[i] + a[i];
    }
    vll dp(n + 1, -INFF);
    dp[0] = 0;
    vll new_dp(n + 1, -INFF);
    vector<vi> par_dp(k + 5, vi(n + 1, -1));
    REP(i, k + 1){
        fill(all(new_dp), -INFF);
        hull_trick ht;
        ht.insert({-ps[0], dp[0], 0});
        FOR(j, 1, n + 1, 1){
            pll re = ht.query(ps[n] - ps[j]);
            new_dp[j] = re.ff + ps[j] * (ps[n] - ps[j]);
            par_dp[i][j] = re.ss;
            ht.insert({-ps[j], dp[j], j}); 
        }
        dp.swap(new_dp);
    }
    cout << dp[n] << "\n";
    int lst = n;
    REPD(i, k){
        if(i == 0) break;
        cout << par_dp[i][lst] << " ";
        lst = par_dp[i][lst];
    }
    cout << "\n";
    return 0;
}

Subtask #1
11.0 / 11.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
11.0 / 11.0

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

Subtask #4
17.0 / 17.0

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

Subtask #5
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1004 KB contestant found the optimal answer: 1818678304 == 1818678304
2 Correct 3 ms 1132 KB contestant found the optimal answer: 1326260195 == 1326260195
3 Correct 89 ms 8812 KB contestant found the optimal answer: 4973126687469639 == 4973126687469639
4 Correct 3 ms 1132 KB contestant found the optimal answer: 3748491676694116 == 3748491676694116
5 Correct 68 ms 5740 KB contestant found the optimal answer: 1085432199 == 1085432199
6 Correct 71 ms 6380 KB contestant found the optimal answer: 514790755404 == 514790755404
7 Correct 86 ms 6892 KB contestant found the optimal answer: 1256105310476641 == 1256105310476641
8 Correct 60 ms 5868 KB contestant found the optimal answer: 3099592898816 == 3099592898816
9 Correct 70 ms 6380 KB contestant found the optimal answer: 1241131419367412 == 1241131419367412
10 Correct 105 ms 8044 KB contestant found the optimal answer: 1243084101967798 == 1243084101967798

Subtask #6
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 7268 KB contestant found the optimal answer: 19795776960 == 19795776960
2 Correct 30 ms 7652 KB contestant found the optimal answer: 19874432173 == 19874432173
3 Correct 949 ms 85348 KB contestant found the optimal answer: 497313449256899208 == 497313449256899208
4 Correct 29 ms 8036 KB contestant found the optimal answer: 374850090734572421 == 374850090734572421
5 Correct 1032 ms 84964 KB contestant found the optimal answer: 36183271951 == 36183271951
6 Correct 692 ms 61284 KB contestant found the optimal answer: 51629847150471 == 51629847150471
7 Correct 796 ms 65636 KB contestant found the optimal answer: 124074747024496432 == 124074747024496432
8 Correct 635 ms 54628 KB contestant found the optimal answer: 309959349080800 == 309959349080800
9 Correct 682 ms 61540 KB contestant found the optimal answer: 124113525649823701 == 124113525649823701
10 Correct 882 ms 77284 KB contestant found the optimal answer: 124309619349406845 == 124309619349406845