Submission #1266183

#	Time	Username	Problem	Language	Result	Execution time	Memory
1266183		_rain_	Discharging (NOI20_discharging)	C++17	100 / 100	86 ms	19888 KiB

Discharging

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

#define FOR(i , a , b) for(int i = (a) , _b = (b); i <= _b; ++i)
#define sz(x) (int)(x).size()
#define BIT(mask , x) (((mask) >> (x)) & (1))
#define MASK(x) ((LL)(1)<<(x))
#define TIME_USED cerr << endl << "TIME LAPSED : " << 1.0 * clock() / CLOCKS_PER_SEC << "s" << endl;

template<class T1 , class T2>
	bool maximize(T1 &a , T2 b){
		if (a < b) return a = b , true; else return false;
	}
template<class T1 , class T2>
	bool minimize(T1 &a , T2 b){
		if (a > b) return a = b , true; else return false;
	}
template<class T>
	void compress(vector<T>&data){
		sort(data.begin() , data.end());
		data.resize(unique(data.begin() , data.end()) - data.begin());
	}
template<class T1 , class T2>
	T2 Find(const vector<T1>&data , T2 y){
		return upper_bound(data.begin() , data.end() , y) - data.begin();
	}
	
const int N = (int) 1e6;
const LL inf = (LL) 1e18;
	int n , a[N + 2];

namespace subtask2{
	bool check(){
		return true;
	}
	
	struct Line {
		LL a , b , id;
		Line(LL a , LL b , LL id) : a(a) , b(b) , id(id) {};
	};
	
	class Convex_Hull{
	public:
		
		long double get_intersec(Line x , Line y){
			return (long double)(y.b - x.b) / (long double)(x.a - y.a);
		}
		
		bool cmp1(Line a , Line b , Line c){
			return get_intersec(a , b) > get_intersec(a ,c);
		}
		
		bool cmp2(Line a , Line b , LL x){
			return get_intersec(a ,b) <= x;
		}
		
		LL F(Line a , LL x){
			return a.a * x + a.b;
		}
		
		vector<Line> lines;
		int ptr = 0;
		
			void add_line(Line x){
				int size = sz(lines);
				while (size > 1 && cmp1(lines[size - 2] , lines[size - 1] , x)){
					--size;
					lines.pop_back();
				}
				lines.push_back(x);
			}
			
			int Find_index(int x){
				int low = 0 , high = sz(lines) - 1 , pos = sz(lines);
				while (low <= high){
					int mid = (low + high) / 2;
					if (lines[mid].id >= x) pos = mid , high = mid - 1;
						else low = mid + 1;
				}
				return pos + 1;
			}
			
			LL Find(int limit , LL x , bool de = false){
				int low = Find_index(limit) , high = sz(lines) - 1;
				int pos = low - 1;
				
				
				
				while (low <= high){
					int mid = (low + high) / 2;
					if (cmp2(lines[mid - 1] , lines[mid] , x)){
						pos = mid;
						low = mid + 1;
					}
					else high = mid - 1;
				}
				
//				if (de){
//					for(auto& x : lines) cout << x.a << ' ' << x.b << ' ' << x.id << '\n';
//					cout << pos << '\n';
//				}
				
				if (pos == sz(lines)) return inf;
				return F(lines[pos] , x);
			}
			
			void insert(LL a , LL b , LL id){
				add_line(Line(a , b , id));
			}
	};
	Convex_Hull cover;
	
	int lef[N + 2] = {};
	LL dp[N + 2] = {};
	
	void main_code(){
		vector<int> st;
		FOR(i , 1 , n) {
			while (st.size() && a[st.back()] <= a[i]) st.pop_back();
			if (st.size()) lef[i] = st.back() ; else lef[i] = 0;
			st.push_back(i);
		}
		
		memset(dp , -0x3f , sizeof dp);
		cover.insert(0 , 0 , 0);
		dp[0] = 0;
//		for(int i = 1; i <= n; ++i) cout << lef[i] << ' '; cout << '\n';
		for(int i = 1; i <= n; ++i){
			LL t = cover.Find(lef[i] , a[i] , i == 4);
		
			dp[i] =  t + (LL)n * a[i];
			if (lef[i] != 0) dp[i] = min(dp[i] , dp[lef[i]]);
			cover.insert(-i , dp[i] , i);
		}
		
		cout << dp[n];
	}
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0) ; cout.tie(0);
	#define name "main"
		if (fopen(name".inp","r")){
			freopen(name".inp","r",stdin);
			freopen(name".out","w",stdout);
		}
		
		cin >> n;
		FOR(i , 1 , n) cin >> a[i];
		if (subtask2::check()) return subtask2::main_code() , 0;
	TIME_USED;
}

Compilation message (stderr)

Discharging.cpp: In function 'int main()':
Discharging.cpp:146:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  146 |                         freopen(name".inp","r",stdin);
      |                         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
Discharging.cpp:147:32: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  147 |                         freopen(name".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