Submission #716851

#	Time	Username	Problem	Language	Result	Execution time	Memory
716851		vjudge1	Split the sequence (APIO14_sequence)	C++17	Compilation error	0 ms	0 KiB

sequence

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef double ld;
const int maxn = 5e5 + 100;
const int mod = (int)1e9+7;
int n, k;
int a[maxn];
ll pref[maxn];
ll dp[maxn][202];
int p[maxn][202];
ll d[maxn];
ld inter(int i, int j) {
    return (ld)(d[i] - d[j])/(ld)(pref[j] - pref[i]);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        pref[i] = pref[i-1] + a[i];
    }
    for(int i = 1; i <= n; i++) {
        dp[i][0] = 0;
    }
    for(int it = 1; it <= k; it++) {
        int j = 0;
        for(int i = 0; i <= n; i++) {
            d[i] = dp[i][it-1]  - pref[i]*pref[i];
        }
        vector<int> st;
        st.push_back(0);
        for(int i = 1; i <= n; i++) {
            if(j >= st.size()) {
                j = (int)st.size() - 1;
            }
            while(j > 0 && d[st[j]] + pref[i] * pref[st[j]] < d[st[j-1]] + pref[i] * pref[st[j-1]]) j--;
            while(j + 1 < st.size() && d[st[j]] + pref[i] * pref[st[j]] <= d[st[j+1]] + pref[i] * pref[st[j+1]]) j++;
            int t = st[j];
            p[i][it] = t;
            dp[i][it] = pref[t] * pref[i] + d[t];
            int sz = (int)st.size();
            while(sz > 0 && pref[i] == pref[st[sz-1]]) {
                st.pop_back();
                sz--;
            }
            while(sz > 1 && inter(st[sz - 1], st[sz-2]) > inter(st[sz-2], i)) {
                st.pop_back();
                sz--;
            }
            st.push_back(i);
        }

    }
    vector<int> cur;
    int last = n;

    for(int i = k; i >= 1; i--) {
        last = p[last][i];
        cur.push_back(last);
    }
    cout << dp[n][k] << "\n";
    reverse(cur.begin(), cur.end());
    for(int x: cur) cout << x << " ";
}#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef double ld;
const int maxn = 5e5 + 100;
const int mod = (int)1e9+7;
int n, k;
int a[maxn];
ll pref[maxn];
ll dp[maxn][202];
int p[maxn][202];
ll d[maxn];
ld inter(int i, int j) {
    return (ld)(d[i] - d[j])/(ld)(pref[j] - pref[i]);
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> k;
    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        pref[i] = pref[i-1] + a[i];
    }
    for(int i = 1; i <= n; i++) {
        dp[i][0] = 0;
    }
    for(int it = 1; it <= k; it++) {
        int j = 0;
        for(int i = 0; i <= n; i++) {
            d[i] = dp[i][it-1]  - pref[i]*pref[i];
        }
        vector<int> st;
        st.push_back(0);
        for(int i = 1; i <= n; i++) {
            if(j >= st.size()) {
                j = (int)st.size() - 1;
            }
            while(j > 0 && d[st[j]] + pref[i] * pref[st[j]] < d[st[j-1]] + pref[i] * pref[st[j-1]]) j--;
            while(j + 1 < st.size() && d[st[j]] + pref[i] * pref[st[j]] <= d[st[j+1]] + pref[i] * pref[st[j+1]]) j++;
            int t = st[j];
            p[i][it] = t;
            dp[i][it] = pref[t] * pref[i] + d[t];
            int sz = (int)st.size();
            while(sz > 0 && pref[i] == pref[st[sz-1]]) {
                st.pop_back();
                sz--;
            }
            while(sz > 1 && inter(st[sz - 1], st[sz-2]) > inter(st[sz-2], i)) {
                st.pop_back();
                sz--;
            }
            st.push_back(i);
        }

    }
    vector<int> cur;
    int last = n;

    for(int i = k; i >= 1; i--) {
        last = p[last][i];
        cur.push_back(last);
    }
    cout << dp[n][k] << "\n";
    reverse(cur.begin(), cur.end());
    for(int x: cur) cout << x << " ";
}

Compilation message (stderr)

sequence.cpp:68:2: error: stray '#' in program
   68 | }#include <bits/stdc++.h>
      |  ^
sequence.cpp: In function 'int main()':
sequence.cpp:37:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   37 |             if(j >= st.size()) {
      |                ~~^~~~~~~~~~~~
sequence.cpp:41:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |             while(j + 1 < st.size() && d[st[j]] + pref[i] * pref[st[j]] <= d[st[j+1]] + pref[i] * pref[st[j+1]]) j++;
      |                   ~~~~~~^~~~~~~~~~~
sequence.cpp: At global scope:
sequence.cpp:68:3: error: 'include' does not name a type
   68 | }#include <bits/stdc++.h>
      |   ^~~~~~~
sequence.cpp:73:11: error: redefinition of 'const int maxn'
   73 | const int maxn = 5e5 + 100;
      |           ^~~~
sequence.cpp:6:11: note: 'const int maxn' previously defined here
    6 | const int maxn = 5e5 + 100;
      |           ^~~~
sequence.cpp:74:11: error: redefinition of 'const int mod'
   74 | const int mod = (int)1e9+7;
      |           ^~~
sequence.cpp:7:11: note: 'const int mod' previously defined here
    7 | const int mod = (int)1e9+7;
      |           ^~~
sequence.cpp:75:5: error: redefinition of 'int n'
   75 | int n, k;
      |     ^
sequence.cpp:8:5: note: 'int n' previously declared here
    8 | int n, k;
      |     ^
sequence.cpp:75:8: error: redefinition of 'int k'
   75 | int n, k;
      |        ^
sequence.cpp:8:8: note: 'int k' previously declared here
    8 | int n, k;
      |        ^
sequence.cpp:76:5: error: redefinition of 'int a [500100]'
   76 | int a[maxn];
      |     ^
sequence.cpp:9:5: note: 'int a [500100]' previously declared here
    9 | int a[maxn];
      |     ^
sequence.cpp:77:4: error: redefinition of 'll pref [500100]'
   77 | ll pref[maxn];
      |    ^~~~
sequence.cpp:10:4: note: 'll pref [500100]' previously declared here
   10 | ll pref[maxn];
      |    ^~~~
sequence.cpp:78:4: error: redefinition of 'll dp [500100][202]'
   78 | ll dp[maxn][202];
      |    ^~
sequence.cpp:11:4: note: 'll dp [500100][202]' previously declared here
   11 | ll dp[maxn][202];
      |    ^~
sequence.cpp:79:5: error: redefinition of 'int p [500100][202]'
   79 | int p[maxn][202];
      |     ^
sequence.cpp:12:5: note: 'int p [500100][202]' previously declared here
   12 | int p[maxn][202];
      |     ^
sequence.cpp:80:4: error: redefinition of 'll d [500100]'
   80 | ll d[maxn];
      |    ^
sequence.cpp:13:4: note: 'll d [500100]' previously declared here
   13 | ll d[maxn];
      |    ^
sequence.cpp:81:4: error: redefinition of 'ld inter(int, int)'
   81 | ld inter(int i, int j) {
      |    ^~~~~
sequence.cpp:14:4: note: 'ld inter(int, int)' previously defined here
   14 | ld inter(int i, int j) {
      |    ^~~~~
sequence.cpp:84:5: error: redefinition of 'int main()'
   84 | int main() {
      |     ^~~~
sequence.cpp:17:5: note: 'int main()' previously defined here
   17 | int main() {
      |     ^~~~
sequence.cpp: In function 'int main()':
sequence.cpp:104:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |             if(j >= st.size()) {
      |                ~~^~~~~~~~~~~~
sequence.cpp:108:25: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |             while(j + 1 < st.size() && d[st[j]] + pref[i] * pref[st[j]] <= d[st[j+1]] + pref[i] * pref[st[j+1]]) j++;
      |                   ~~~~~~^~~~~~~~~~~