제출 #1281653

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1281653		herominhsteve	Discharging (NOI20_discharging)	C++20	100 / 100	80 ms	12196 KiB

Discharging

#include <bits/stdc++.h>
#define el '\n'
#define FNAME "NOI20_discharging"
#define allof(x) x.begin(),x.end()
#define allof1(x) x.begin()+1,x.end()
#define mset(x,n) memset(x,(n),sizeof(x))
using namespace std;
const long long MOD = (long long) 1e9 + 7;
template<class X,class Y> bool minimize(X &a,Y b){ if (a>b) {a=b; return true;} return false;}
template<class X,class Y> bool maximize(X &a,Y b){ if (a<b) {a=b; return true;} return false;}

void setup(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
	if (fopen(FNAME".inp","r")){
		freopen(FNAME".inp","r",stdin);
		freopen(FNAME".out","w",stdout);
	}
}

const long long INF = (long long) 1e16 + 15092007;

struct MinHull{
	struct Line{
		long long a,b;
		Line():a(0),b(0) {}
		Line(long long A,long long B):a(A),b(B) {}
		friend double getIntersection(const Line &x, const Line &y){
			return 1.0 * (y.b - x.b) / (x.a - y.a);
		}
		friend bool overlap(Line A,Line B,Line C){
			return getIntersection(B,C) < getIntersection(A,C);
		}
		long long evaluate(long long x){
			return a * x + b;
		}
	};

	vector<Line> lines;
	vector<double> bubble;

	void addLine(long long a, long long b){
		Line newLine = Line(a,b);
		while (lines.size() >= 2 and overlap(lines[lines.size()-2], lines.back(), newLine)){
			lines.pop_back();
			bubble.pop_back();
		}
		if (!lines.empty()){
			bubble.emplace_back(getIntersection(lines.back() , newLine));
		}
		lines.emplace_back(newLine);
	}

	long long getVal(long long x){
		int pos = lower_bound(allof(bubble),x) - bubble.begin();
		return lines[pos].evaluate(x);
	}

};

int n;
vector<int> a;

void init(){
	cin>>n;
	a.assign(n+1,0);
	for (int i=1;i<=n;i++) cin>>a[i];
	for (int i=1;i<=n;i++) maximize(a[i],a[i-1]);
}

namespace DPNaive{
	void solve(){
		vector<long long> dp(n+1,INF);
		dp[0] = 0;
		for (int i=1;i<=n;i++){
			for (int j=i;j>=1;j--){
				minimize(dp[i] , dp[j-1] + 1ll * a[i] * (n - j + 1));
			}
		}
		cout<<dp[n];
		exit(0);
	}	
};

/*
 * dp[i] = min_j (dp[j-1] + a[i] * (n - j + 1))
 * 		 = min_j (dp[j-1] - j * a[i]) + a[i] * (n + 1)
 * into CHT: -j * a[i] + dp[j-1]
 * a = -j; x = a[i]; b = dp[j-1] (y = ax + b)
*/

namespace ConvexHullTrick{
	void solve(){
		MinHull cht;
		vector<long long> dp(n+1,INF);
		dp[0] = 0;
		for (int i=1;i<=n;i++){
			cht.addLine(-i , dp[i-1]);
			dp[i] = cht.getVal(a[i]) + 1ll * a[i] * (n+1);
		}
		cout<<dp[n];
	}
};

void sol(){
	// if (n <= 1000) DPNaive::solve();
	ConvexHullTrick::solve();
}

int main(){
    setup();
    init();
    sol();
}

컴파일 시 표준 에러 (stderr) 메시지

Discharging.cpp: In function 'void setup()':
Discharging.cpp:16:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   16 |                 freopen(FNAME".inp","r",stdin);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
Discharging.cpp:17:24: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |                 freopen(FNAME".out","w",stdout);
      |                 ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 13 / 13
• Subtask 3: 25 / 25
• Subtask 4: 11 / 11
• Subtask 5: 14 / 14
• Subtask 6: 28 / 28