Submission #114167

#	Time	Username	Problem	Language	Result	Execution time	Memory
114167		TAMREF	Can polan into space? (OJUZ11_space)	C++11	100 / 100	127 ms	28664 KiB

space

#include <bits/stdc++.h>
#define va first
#define vb second
#define lb lower_bound
#define ub upper_bound
#define pp push_back
#define ep emplace_back
#define all(v) (v).begin(),(v).end()
#define szz(v) ((int)(v).size())
#define psm partial_sum
#define acm accumulate
#define fio ios_base::sync_with_stdio(0);cin.tie(0);
using namespace std;
using ll = long long; using lf = long double;
using pii = pair<int,int>; using ppi = pair<int,pii>;
using pss = pair<short,short>; using pll = pair<ll,ll>;
const lf PI = 3.14159265358979323846264338L;
template <typename T>
inline T umax(T& u, T v){return u = max(u, v);}
template <typename T>
inline T umin(T& u, T v){return u = min(u, v);}

ll d[200005][4];
char b[200005][4];
char ideg[200005]; 
// 0 = <<, 1 = <>, 2 = ><, 3 = >>
int a[200005][3];
int n;
vector<int> G[200005];

void dp_eval(ll& dp, char &bp, ll dv, char bv){
    if(dp < dv){
        dp = dv;
        bp = bv;
    }
}

int main(){
    fio;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i][0] >> a[i][1] >> a[i][2];
    }
    d[1][0] = a[1][1];
    d[1][1] = a[1][0];
    d[1][2] = -LLONG_MAX;
    d[1][3] = -LLONG_MAX;
    for(int i = 2; i <= n; i++){
        for(int k = 0; k < 8; k++){
            int from = (k >> 1) & 3, to = k & 3;
            dp_eval(d[i][to], b[i][to], d[i-1][from] + a[i][to/2 + !(to&1)], from);
        }
    }
    int now;
    if(d[n][1] > d[n][3]){
        cout << d[n][1] << '\n';
        now = 1;
    }else{
        cout << d[n][3] << '\n';
        now = 3;
    }
    queue<int> q;
    for(int i = n; i >= 1; i--){
        if(now & 1){
            if(i + 1 <= n){
                G[i].pp(i+1);
                ++ideg[i+1];
            }
        }
        if(now < 2){
            if(i - 1){
                G[i].pp(i-1);
                ++ideg[i-1];
            }
        }
        if(now == 1){
            q.push(i);
        }
        now = b[i][now];
    }
    while(q.size()){
        int f = q.front(); q.pop();
        cout << f << ' ';
        for(int u : G[f]){
            --ideg[u];
            if(!ideg[u]) q.push(u);
        }
    }
}

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