Submission #20502

#	Time	Username	Problem	Language	Result	Execution time	Memory
20502		안녕하세요 투어리스트입니다 진짜에요 (#35)	Can polan into space? (OJUZ11_space)	C++14	0 / 100	146 ms	17684 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);

void shift(int x){
	c[x]=b[x]; b[x]=a[x]; a[x]=-inf;
}

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);
		}
    }
    
    vector<pp> av;
    for(int i=1; i<=n; ++i) av.pb({use[i], i});
    ll test_ans = 0;
    sort(all(av)); for(auto X:av){
    	int x=X.second;
    	if(adjc[x] == 0) assert(use[x]==1), test_ans += a[x];
    	if(adjc[x] == 1) assert(use[x]==2), test_ans += b[x];
    	if(adjc[x] == 2) assert(use[x]==3), test_ans += c[x];
    	++adjc[x-1];
    	++adjc[x+1];
    	printf("%d ", x);
    }
    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: 0 / 11
• Subtask 2: 0 / 12
• Subtask 3: 0 / 23
• Subtask 4: 0 / 26
• Subtask 5: 0 / 28