Submission #698204

#	Time	Username	Problem	Language	Result	Execution time	Memory
698204		tvladm2009	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;
#define int usigned long long 
const int N = (int) 1e5 + 7;
const int K = (int) 2e2 + 7;
int a[N], sp[N], dp[N][K], rec[N][K];

struct Line {
  int a;
  int b;
  int ind;

  int eval(int x) {
    return a * x + b;
  }
};

struct Fraction {
  int num;
  ll den;
};

Fraction x(Line l1, Line l2) {
  // l1.a * x + l1.b = y
  // l2.a * x + l2.b = y

  // l1.a * x + l1.b = l2.a * x + l2.b
  // l1.a * x - l2.b * x = l2.b - l1.b
  // (l1.a - l2.b) * x = l2.b - l1.b

  // x = (l2.b - l1.b) / (l1.a - l2.a)

  if (l1.a - l2.a > 0) {
    return {l2.b - l1.b, l1.a - l2.a};
  } else {
    return {-(l2.b - l1.b), -(l1.a - l2.a)};
  }
}

bool operator <= (const Fraction &a, const Fraction &b) {
  return a.num * b.den <= a.den * b.num;
}

deque<Line> DS;

void add(Line line) {
  while ((int) DS.size() >= 2 && x(DS.end()[-1], line) <= x(DS.end()[-2], DS.end()[-1])) {
    DS.pop_back();
  }
  DS.push_back(line);
}

pair<ll, int> query(int x) {
  while ((int) DS.size() >= 2 && DS[0].eval(x) <= DS[1].eval(x)) {
    DS.pop_front();
  }
  return {DS[0].eval(x), DS[0].ind};
}

void solve(int layer, int n) {
  DS.clear();
  for (int i = layer; i <= n; i++) {
    add({sp[i - 1], dp[layer - 1][i - 1] - sp[i - 1] * sp[i - 1], i - 1});
    pair<int, int> aux = query(sp[i]);
    dp[layer][i] = aux.first;
    rec[layer][i] = aux.second;
  }
}

signed main() {
  ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

  int n, k;
  cin >> n >> k;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  for (int i = 1; i <= n; i++) {
    sp[i] = sp[i - 1] + a[i];
    dp[1][i] = 0;
  }
  for (int i = 2; i <= k + 1; i++) {
    solve(i, n);
  }

  cout << dp[k + 1][n] << "\n";
  vector<int> sol;
  int aux = rec[k + 1][n];
  while (k > 0) {
    sol.push_back(aux);
    aux = rec[k][aux];
    k--;
  }
  reverse(sol.begin(), sol.end());
  for (auto &it : sol) {
    cout << it << " ";
  }
  return 0;
}

Compilation message (stderr)

sequence.cpp:6:13: error: 'usigned' does not name a type; did you mean 'signed'?
    6 | #define int usigned long long
      |             ^~~~~~~
sequence.cpp:7:7: note: in expansion of macro 'int'
    7 | const int N = (int) 1e5 + 7;
      |       ^~~
sequence.cpp:6:13: error: 'usigned' does not name a type; did you mean 'signed'?
    6 | #define int usigned long long
      |             ^~~~~~~
sequence.cpp:8:7: note: in expansion of macro 'int'
    8 | const int K = (int) 2e2 + 7;
      |       ^~~
sequence.cpp:6:13: error: 'usigned' does not name a type; did you mean 'signed'?
    6 | #define int usigned long long
      |             ^~~~~~~
sequence.cpp:9:1: note: in expansion of macro 'int'
    9 | int a[N], sp[N], dp[N][K], rec[N][K];
      | ^~~
sequence.cpp:6:13: error: 'usigned' does not name a type; did you mean 'signed'?
    6 | #define int usigned long long
      |             ^~~~~~~
sequence.cpp:12:3: note: in expansion of macro 'int'
   12 |   int a;
      |   ^~~
sequence.cpp:6:13: error: 'usigned' does not name a type; did you mean 'signed'?
    6 | #define int usigned long long
      |             ^~~~~~~
sequence.cpp:13:3: note: in expansion of macro 'int'
   13 |   int b;
      |   ^~~
sequence.cpp:6:13: error: 'usigned' does not name a type; did you mean 'signed'?
    6 | #define int usigned long long
      |             ^~~~~~~
sequence.cpp:14:3: note: in expansion of macro 'int'
   14 |   int ind;
      |   ^~~
sequence.cpp:6:13: error: 'usigned' does not name a type; did you mean 'signed'?
    6 | #define int usigned long long
      |             ^~~~~~~
sequence.cpp:16:3: note: in expansion of macro 'int'
   16 |   int eval(int x) {
      |   ^~~
sequence.cpp:6:13: error: 'usigned' does not name a type; did you mean 'signed'?
    6 | #define int usigned long long
      |             ^~~~~~~
sequence.cpp:22:3: note: in expansion of macro 'int'
   22 |   int num;
      |   ^~~
sequence.cpp: In function 'Fraction x(Line, Line)':
sequence.cpp:36:10: error: 'struct Line' has no member named 'a'
   36 |   if (l1.a - l2.a > 0) {
      |          ^
sequence.cpp:36:17: error: 'struct Line' has no member named 'a'
   36 |   if (l1.a - l2.a > 0) {
      |                 ^
sequence.cpp:37:16: error: 'struct Line' has no member named 'b'
   37 |     return {l2.b - l1.b, l1.a - l2.a};
      |                ^
sequence.cpp:37:23: error: 'struct Line' has no member named 'b'
   37 |     return {l2.b - l1.b, l1.a - l2.a};
      |                       ^
sequence.cpp:37:29: error: 'struct Line' has no member named 'a'
   37 |     return {l2.b - l1.b, l1.a - l2.a};
      |                             ^
sequence.cpp:37:36: error: 'struct Line' has no member named 'a'
   37 |     return {l2.b - l1.b, l1.a - l2.a};
      |                                    ^
sequence.cpp:37:37: error: could not convert '{<expression error>, <expression error>}' from '<brace-enclosed initializer list>' to 'Fraction'
   37 |     return {l2.b - l1.b, l1.a - l2.a};
      |                                     ^
      |                                     |
      |                                     <brace-enclosed initializer list>
sequence.cpp:39:18: error: 'struct Line' has no member named 'b'
   39 |     return {-(l2.b - l1.b), -(l1.a - l2.a)};
      |                  ^
sequence.cpp:39:25: error: 'struct Line' has no member named 'b'
   39 |     return {-(l2.b - l1.b), -(l1.a - l2.a)};
      |                         ^
sequence.cpp:39:34: error: 'struct Line' has no member named 'a'
   39 |     return {-(l2.b - l1.b), -(l1.a - l2.a)};
      |                                  ^
sequence.cpp:39:41: error: 'struct Line' has no member named 'a'
   39 |     return {-(l2.b - l1.b), -(l1.a - l2.a)};
      |                                         ^
sequence.cpp:39:43: error: could not convert '{<expression error>, <expression error>}' from '<brace-enclosed initializer list>' to 'Fraction'
   39 |     return {-(l2.b - l1.b), -(l1.a - l2.a)};
      |                                           ^
      |                                           |
      |                                           <brace-enclosed initializer list>
sequence.cpp: In function 'bool operator<=(const Fraction&, const Fraction&)':
sequence.cpp:44:12: error: 'const struct Fraction' has no member named 'num'
   44 |   return a.num * b.den <= a.den * b.num;
      |            ^~~
sequence.cpp:44:37: error: 'const struct Fraction' has no member named 'num'
   44 |   return a.num * b.den <= a.den * b.num;
      |                                     ^~~
sequence.cpp: In function 'void add(Line)':
sequence.cpp:6:13: error: 'usigned' was not declared in this scope; did you mean 'signed'?
    6 | #define int usigned long long
      |             ^~~~~~~
sequence.cpp:50:11: note: in expansion of macro 'int'
   50 |   while ((int) DS.size() >= 2 && x(DS.end()[-1], line) <= x(DS.end()[-2], DS.end()[-1])) {
      |           ^~~
sequence.cpp:6:21: error: expected ')' before 'long'
    6 | #define int usigned long long
      |                     ^~~~
sequence.cpp:50:11: note: in expansion of macro 'int'
   50 |   while ((int) DS.size() >= 2 && x(DS.end()[-1], line) <= x(DS.end()[-2], DS.end()[-1])) {
      |           ^~~
sequence.cpp:50:10: note: to match this '('
   50 |   while ((int) DS.size() >= 2 && x(DS.end()[-1], line) <= x(DS.end()[-2], DS.end()[-1])) {
      |          ^
sequence.cpp:52:4: error: expected ')' before 'DS'
   52 |   }
      |    ^
      |    )
   53 |   DS.push_back(line);
      |   ~~
sequence.cpp:50:9: note: to match this '('
   50 |   while ((int) DS.size() >= 2 && x(DS.end()[-1], line) <= x(DS.end()[-2], DS.end()[-1])) {
      |         ^
sequence.cpp: At global scope:
sequence.cpp:6:13: error: 'usigned' was not declared in this scope; did you mean 'signed'?
    6 | #define int usigned long long
      |             ^~~~~~~
sequence.cpp:56:10: note: in expansion of macro 'int'
   56 | pair<ll, int> query(int x) {
      |          ^~~
sequence.cpp:56:13: error: template argument 2 is invalid
   56 | pair<ll, int> query(int x) {
      |             ^
sequence.cpp:6:13: error: 'usigned' was not declared in this scope; did you mean 'signed'?
    6 | #define int usigned long long
      |             ^~~~~~~
sequence.cpp:56:21: note: in expansion of macro 'int'
   56 | pair<ll, int> query(int x) {
      |                     ^~~
sequence.cpp:63:6: error: variable or field 'solve' declared void
   63 | void solve(int layer, int n) {
      |      ^~~~~
sequence.cpp:6:13: error: 'usigned' was not declared in this scope; did you mean 'signed'?
    6 | #define int usigned long long
      |             ^~~~~~~
sequence.cpp:63:12: note: in expansion of macro 'int'
   63 | void solve(int layer, int n) {
      |            ^~~
sequence.cpp:6:13: error: 'usigned' was not declared in this scope; did you mean 'signed'?
    6 | #define int usigned long long
      |             ^~~~~~~
sequence.cpp:63:23: note: in expansion of macro 'int'
   63 | void solve(int layer, int n) {
      |                       ^~~
sequence.cpp: In function 'int main()':
sequence.cpp:6:13: error: 'usigned' was not declared in this scope; did you mean 'signed'?
    6 | #define int usigned long long
      |             ^~~~~~~
sequence.cpp:76:3: note: in expansion of macro 'int'
   76 |   int n, k;
      |   ^~~
sequence.cpp:77:10: error: 'n' was not declared in this scope
   77 |   cin >> n >> k;
      |          ^
sequence.cpp:77:15: error: 'k' was not declared in this scope
   77 |   cin >> n >> k;
      |               ^
sequence.cpp:6:21: error: expected ';' before 'long'
    6 | #define int usigned long long
      |                     ^~~~
sequence.cpp:78:8: note: in expansion of macro 'int'
   78 |   for (int i = 1; i <= n; i++) {
      |        ^~~
sequence.cpp:78:19: error: 'i' was not declared in this scope
   78 |   for (int i = 1; i <= n; i++) {
      |                   ^
sequence.cpp:79:12: error: 'a' was not declared in this scope
   79 |     cin >> a[i];
      |            ^
sequence.cpp:6:21: error: expected ';' before 'long'
    6 | #define int usigned long long
      |                     ^~~~
sequence.cpp:81:8: note: in expansion of macro 'int'
   81 |   for (int i = 1; i <= n; i++) {
      |        ^~~
sequence.cpp:81:19: error: 'i' was not declared in this scope
   81 |   for (int i = 1; i <= n; i++) {
      |                   ^
sequence.cpp:82:5: error: 'sp' was not declared in this scope
   82 |     sp[i] = sp[i - 1] + a[i];
      |     ^~
sequence.cpp:82:25: error: 'a' was not declared in this scope
   82 |     sp[i] = sp[i - 1] + a[i];
      |                         ^
sequence.cpp:83:5: error: 'dp' was not declared in this scope
   83 |     dp[1][i] = 0;
      |     ^~
sequence.cpp:6:21: error: expected ';' before 'long'
    6 | #define int usigned long long
      |                     ^~~~
sequence.cpp:85:8: note: in expansion of macro 'int'
   85 |   for (int i = 2; i <= k + 1; i++) {
      |        ^~~
sequence.cpp:85:19: error: 'i' was not declared in this scope
   85 |   for (int i = 2; i <= k + 1; i++) {
      |                   ^
sequence.cpp:86:5: error: 'solve' was not declared in this scope
   86 |     solve(i, n);
      |     ^~~~~
sequence.cpp:89:11: error: 'dp' was not declared in this scope
   89 |   cout << dp[k + 1][n] << "\n";
      |           ^~
sequence.cpp:90:13: error: template argument 2 is invalid
   90 |   vector<int> sol;
      |             ^
sequence.cpp:6:21: error: expected ';' before 'long'
    6 | #define int usigned long long
      |                     ^~~~
sequence.cpp:91:3: note: in expansion of macro 'int'
   91 |   int aux = rec[k + 1][n];
      |   ^~~
sequence.cpp:93:9: error: request for member 'push_back' in 'sol', which is of non-class type 'int'
   93 |     sol.push_back(aux);
      |         ^~~~~~~~~
sequence.cpp:93:19: error: 'aux' was not declared in this scope
   93 |     sol.push_back(aux);
      |                   ^~~
sequence.cpp:94:11: error: 'rec' was not declared in this scope
   94 |     aux = rec[k][aux];
      |           ^~~
sequence.cpp:97:15: error: request for member 'begin' in 'sol', which is of non-class type 'int'
   97 |   reverse(sol.begin(), sol.end());
      |               ^~~~~
sequence.cpp:97:28: error: request for member 'end' in 'sol', which is of non-class type 'int'
   97 |   reverse(sol.begin(), sol.end());
      |                            ^~~
sequence.cpp:98:19: error: 'begin' was not declared in this scope
   98 |   for (auto &it : sol) {
      |                   ^~~
sequence.cpp:98:19: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from sequence.cpp:1:
/usr/include/c++/10/valarray:1224:5: note:   'std::begin'
 1224 |     begin(const valarray<_Tp>& __va)
      |     ^~~~~
In file included from /usr/include/c++/10/filesystem:46,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:129,
                 from sequence.cpp:1:
/usr/include/c++/10/bits/fs_dir.h:549:3: note:   'std::filesystem::__cxx11::begin'
  549 |   begin(recursive_directory_iterator __iter) noexcept
      |   ^~~~~
sequence.cpp:98:19: error: 'end' was not declared in this scope
   98 |   for (auto &it : sol) {
      |                   ^~~
sequence.cpp:98:19: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:95,
                 from sequence.cpp:1:
/usr/include/c++/10/valarray:1244:5: note:   'std::end'
 1244 |     end(const valarray<_Tp>& __va)
      |     ^~~
In file included from /usr/include/c++/10/filesystem:46,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:129,
                 from sequence.cpp:1:
/usr/include/c++/10/bits/fs_dir.h:554:3: note:   'std::filesystem::__cxx11::end'
  554 |   end(recursive_directory_iterator) noexcept
      |   ^~~