Submission #20450

#	Time	Username	Problem	Language	Result	Execution time	Memory
20450		mistake (#35)	Can polan into space? (OJUZ11_space)	C++14	100 / 100	163 ms	39456 KiB

space

#include <cstdio>
#include <cstdlib>
#include <cassert>
#include <cstring>
#include <iostream>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <set>
#include <map>
#include <complex>

#define mp(a, b) make_pair((a), (b))
#define pb(a) push_back((a))
#define pf(a) push_font((a))
#define rb() pop_back()
#define rf() pop_front()
#define sz(a) ((int)a.size())

using namespace std;
 
typedef long long lld;
typedef pair<int, int> pii;
typedef pair<lld, lld> pll;
typedef pair<lld, int> pli;
typedef pair<int, lld> pil;
typedef vector<vector<int>> Matrix;
typedef vector<vector<int>> Adj;
typedef vector<int> Row;
typedef complex<double> Complex;
typedef vector<Complex> Vcomplex;

const int MOD = 1e9 + 7;
const int INF = 1e9;
const lld LINF = 1e18;
const double FINF = 1e15;
const double EPS = 1e-9;
const double PI = 2.0 * acos(0.0);

lld D[200005][2][2];
int pl[200005][2][2];
int pr[200005][2][2];
int n;
int a[200005][3];
int vis[200005];
vector<int> adj[200005];
vector<int> ord;
inline void asmax(lld& x, lld y) {
  if (x < y) x = y;
}

inline void asmax(int i1, int a1, int b1, int i2, int a2, int b2) {
  if (D[i1][a1][b1] < D[i2][a2][b2] + a[i1][a1 + b1]) {
    D[i1][a1][b1] = D[i2][a2][b2] + a[i1][a1 + b1];
    pl[i1][a1][b1] = a2;
    pr[i1][a1][b1] = b2;
  }
}

void dfs(int cur) {
  vis[cur] = true;
  for (int nxt : adj[cur]) {
    if (!vis[nxt]) dfs(nxt);
  }
  ord.pb(cur);
}

int main() {
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    for (int j = 0; j < 3; ++j) {
      scanf("%d", &a[i][j]);
    }
  }
  for (int i = 0; i <= n; ++i) {
    for (int j = 0; j < 2; ++j) {
      for (int k = 0; k < 2; ++k) {
        D[i][j][k] = -LINF;
      }
    }
  }
  D[0][0][1] = 0;
  for (int i = 0; i < n; ++i) {
    asmax(i+1, 1, 0, i, 1, 0);
    asmax(i+1, 1, 1, i, 1, 0);
    asmax(i+1, 1, 0, i, 0, 0);
    asmax(i+1, 1, 1, i, 0, 0);
    asmax(i+1, 0, 0, i, 0, 1);
    asmax(i+1, 0, 1, i, 0, 1);
    asmax(i+1, 0, 0, i, 1, 1);
    asmax(i+1, 0, 1, i, 1, 1);
    /*
    asmax(D[i+1][1][0], D[i][1][0] + b[i+1]); //i -> i+1
    asmax(D[i+1][1][1], D[i][1][0] + c[i+1]); 
    asmax(D[i+1][1][0], D[i][0][0] + b[i+1]);
    asmax(D[i+1][1][1], D[i][0][0] + c[i+1]);
    asmax(D[i+1][0][0], D[i][0][1] + a[i+1]); //i+1 -> i
    asmax(D[i+1][0][1], D[i][0][1] + b[i+1]); 
    asmax(D[i+1][0][0], D[i][1][1] + a[i+1]);
    asmax(D[i+1][0][1], D[i][1][1] + b[i+1]);
    */
  }
  lld ans = max(D[n][1][0], D[n][0][0]);
  int cur = n;
  int l = (ans == D[n][1][0]), r = 0;
  while (cur > 1) {
    if (l == 1) {
      adj[cur-1].pb(cur);
    } else {
      adj[cur].pb(cur-1);
    }
    int nl = pl[cur][l][r];
    int nr = pr[cur][l][r];
    l = nl;
    r = nr;
    --cur;
  }
  for (int i = 1; i <= n; ++i) if (!vis[i]) dfs(i);
  printf("%lld\n", ans);
  for (int i = n-1; i >= 0; --i) {
    printf("%d ", ord[i]);
  }
}

Compilation message (stderr)

space.cpp: In function 'int main()':
space.cpp:72:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &n);
                  ^
space.cpp:75:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d", &a[i][j]);
                            ^

• Subtask 1: 11 / 11
• Subtask 2: 12 / 12
• Subtask 3: 23 / 23
• Subtask 4: 26 / 26
• Subtask 5: 28 / 28