oj.uz

Submission #1095143

# Submission time Handle Problem Language Result Execution time Memory
1095143 2024-10-01T11:35:08 Z RaduM Split the sequence (APIO14_sequence) C++17
11 / 100
 6 ms 3416 KB 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int NMAX = 1005;
const int KMAX = 202;
int v[NMAX];
ll sp[NMAX];
ll dp[NMAX][KMAX];
int last[NMAX][KMAX];

struct line{
    ll slope, yIntercept;
    line() {}
    line(ll slope, ll yIntercept) : slope(slope), yIntercept(yIntercept) {}

    ll val(int x){
        return slope * x + yIntercept;
    }

    ll intersect(const line &other){
        if(slope == other.slope) return 0;
        return (other.yIntercept - yIntercept + slope - other.slope - 1) / (slope - other.slope);
    }
};

struct CHT{
    deque < pair < pair <line, int>, int > > dq;

    void add(line l, int id){
        while(dq.size() > 1 && dq.back().first.second >= dq.back().first.first.intersect(l)) dq.pop_back();
        if(dq.empty()){
            dq.push_back({{l, 0}, id});
            return;
        }
        dq.push_back({{l, dq.back().first.first.intersect(l)}, id});
    }

    pair <int, ll> query(int x){
        while(dq.size() > 1){
            if(dq[1].first.second <= x) dq.pop_front();
            else break;
        }
        return {dq[0].second, dq[0].first.first.val(x)};
    }
};

CHT cht[KMAX];
vector <int> sol;

int main()
{
    int n,i,k,t;
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> k;
    for(i = 1; i <= n; i++){
        cin >> v[i];
        sp[i] = sp[i - 1] + v[i];
    }
    for(i = 1; i <= n; i++){
        dp[i][1] = sp[i] * (sp[n] - sp[i]);
        int val = i;
//        if(i == n) val--;
        for(int e = 2; e <= min(k, val); e++){
            pair <int, ll> r = cht[e - 1].query(sp[i]);
            dp[i][e] = r.second + sp[i] * (sp[n] - sp[i]);
            last[i][e] = r.first;
        }
        for(int e = 1; e <= min(k, val); e++) cht[e].add(line(sp[i], dp[i][e] - sp[i] * sp[n]), i);
    }
    ll mx = 0;
    int poz;
    for(i = 1; i <= n; i++){
        if(dp[i][k] >= mx){
            mx = dp[i][k];
            poz = i;
        }
    }
    sol.push_back(poz);
    while(k > 1){
        sol.push_back(last[poz][k]);
        poz = last[poz][k];
        k--;
    }
    cout << mx << "\n";
    for(auto x : sol) cout << x << " ";
    return 0;
}

/*

7 3
4 1 3 4 0 2 3

*/

Compilation message

sequence.cpp: In function 'int main()':
sequence.cpp:54:15: warning: unused variable 't' [-Wunused-variable]
   54 |     int n,i,k,t;
      |               ^

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB contestant found the optimal answer: 108 == 108
2 Correct 0 ms 604 KB contestant found the optimal answer: 999 == 999
3 Incorrect 0 ms 604 KB Integer 2 violates the range [1, 1]
4 Halted 0 ms 0 KB -

Subtask #2
11.0 / 11.0

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

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 860 KB contestant found the optimal answer: 610590000 == 610590000
2 Correct 0 ms 860 KB contestant found the optimal answer: 311760000 == 311760000
3 Correct 1 ms 1116 KB contestant found the optimal answer: 1989216017013 == 1989216017013
4 Correct 1 ms 860 KB contestant found the optimal answer: 1499437552673 == 1499437552673
5 Incorrect 1 ms 1116 KB contestant didn't find the optimal answer: 1019625812 < 1019625819
6 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2908 KB contestant found the optimal answer: 21503404 == 21503404
2 Correct 1 ms 2904 KB contestant found the optimal answer: 140412195 == 140412195
3 Correct 6 ms 3164 KB contestant found the optimal answer: 49729674225461 == 49729674225461
4 Correct 1 ms 2908 KB contestant found the optimal answer: 37485571387523 == 37485571387523
5 Incorrect 6 ms 3416 KB contestant didn't find the optimal answer: 679388309 < 679388326
6 Halted 0 ms 0 KB -

Subtask #5
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 860 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 29.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 864 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -