Submission #20831

#	Time	Username	Problem	Language	Result	Execution time	Memory
20831		Namnamseo	Can polan into space? (OJUZ11_space)	C++14	100 / 100	139 ms	14520 KiB

space

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pp;
void read(int& x){ scanf("%d",&x); }
void read(ll& x){ scanf("%lld",&x); }
template<typename T,typename... Args>
void read(T& a,Args&... b){ read(a); read(b...); }
#define all(x) (x).begin(),(x).end()
#define pb push_back

int n;
ll a[200010];
ll b[200010];
ll c[200010];

ll inf = (1LL<<60);

ll dp[200010][4];

int use[200010];

#define NOA 0
#define HEA 1
#define AFA 2
#define HEC 3

int adjc[200010];

int main()
{
	//freopen("in", "r", stdin);
    read(n); for(int i=1; i<=n; ++i) read(a[i], b[i], c[i]);
    dp[0][NOA] = 0;
    dp[0][HEA] = -inf;
    dp[0][AFA] = -inf;
    dp[0][HEC] = -inf;
    
    for(int i=1; i<=n; ++i){
		dp[i][NOA] = max(dp[i-1][HEC], dp[i-1][NOA]) + b[i];
		dp[i][HEA] = max(dp[i-1][HEC], dp[i-1][NOA]) + a[i];
		dp[i][AFA] = max(dp[i-1][AFA], dp[i-1][HEA]) + b[i];
		dp[i][HEC] = max(dp[i-1][AFA], dp[i-1][HEA]) + c[i];
    }
    
    ll ans = max(dp[n][AFA], dp[n][HEA]);
    printf("%lld\n", ans);
    int mi=0;
    if(ans == dp[n][AFA]) mi=AFA; else mi=HEA;
    for(int i=n; 1<=i; --i){
		if(mi == NOA){
			use[i]=2;
			mi = (dp[i-1][HEC] > dp[i-1][NOA] ? HEC : NOA);
		} else if(mi == HEA){
			use[i]=1;
			mi = (dp[i-1][HEC] > dp[i-1][NOA] ? HEC : NOA);
		} else if(mi == AFA){
			use[i]=2;
			mi = (dp[i-1][HEA] > dp[i-1][AFA] ? HEA : AFA);
		} else if(mi == HEC){
			use[i]=3;
			mi = (dp[i-1][HEA] > dp[i-1][AFA] ? HEA : AFA);
		}
    }
    
    for(int i=1; i<=n; ++i) if(use[i]==1){
		printf("%d ", i);
		for(int j=i-1; j>=1; --j){
			if(use[j] != 2) break;
			printf("%d ", j);
		}
		for(int j=i+1; j<=n; ++j){
			if(use[j] != 2) break;
			printf("%d ", j);
		}
    }
    for(int i=1; i<=n; ++i) if(use[i]==3){
		printf("%d ", i);
    }
    return 0;
}

Compilation message (stderr)

space.cpp: In function 'void read(int&)':
space.cpp:5:34: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void read(int& x){ scanf("%d",&x); }
                                  ^
space.cpp: In function 'void read(ll&)':
space.cpp:6:35: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
 void read(ll& x){ scanf("%lld",&x); }
                                   ^

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