제출 #584993

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
584993		keta_tsimakuridze	Discharging (NOI20_discharging)	C++17	100 / 100	625 ms	78660 KiB

Discharging

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int,int>
#define f first
#define s second
#define endl "\n"
const int N = 1e6 + 5, mod = 1e9 + 7, inf = mod; //!
int t, pos[N], a[N], bef[N];
map<int,int> id;
int f(int k,int x,int b) {
	return k * x + b;
}
pii tree[4 * N];
void insert(int u,int l,int r, int k,int b) {
	if(l == r) {
		if(f(k, pos[l], b) < f(tree[u].f, pos[l], tree[u].s)) tree[u] = {k, b};
		return;
	}
	int mid = (l + r) / 2;
	if(k < tree[u].f) {
		swap(k, tree[u].f);
		swap(b, tree[u].s);
	}
	if(f(k, pos[mid], b) <= f(tree[u].f, pos[mid], tree[u].s)) {
		insert(2 * u + 1, mid + 1, r, tree[u].f, tree[u].s);
		tree[u].f = k; tree[u].s = b;
		return;
	}
	insert(2 * u, l, mid, k, b);
}
int get(int u,int l,int r,int id) {
	if(l > id || r < id) return inf;
	if(l == r) {
		return f(tree[u].f, pos[l], tree[u].s);
	}
	int mid = (l + r) / 2;
	return min(f(tree[u].f, pos[id], tree[u].s), min(get(2 * u, l, mid, id), get(2 * u + 1, mid + 1,r, id)));
}
main() {
//	ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	int n;
	cin >> n;
	vector<int> x;
	int mx = 0;
	x.push_back(0);
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
		if(a[i] > mx) {
			bef[x.size()] = i - 1;
			x.push_back(i);
			mx = a[i];
			
		}
	}
	bef[x.size()] = n;
	for(int i = 0; i < x.size(); i++) {
		id[x[i]] = i;
		pos[i] = a[x[i]];
	}
	int ANS = 0;
	for(int i = 1; i < x.size(); i++) {
		
		int ans = get(1, 1, x.size() - 1, i) + n * a[x[i]];	
		//cout << i << " __ " <<  get(1, 1, x.size() - 1, i) << " " << (n - bef[i]) * a[x[i]] << " " << ans << endl;
		
	
		if(i + 1 == x.size())  {
			cout << ans;
			return 0;
		}
		insert(1, 1, x.size() - 1, -(x[i + 1] - 1), ans);

	}
	
}

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

Discharging.cpp:40:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   40 | main() {
      | ^~~~
Discharging.cpp: In function 'int main()':
Discharging.cpp:57:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |  for(int i = 0; i < x.size(); i++) {
      |                 ~~^~~~~~~~~~
Discharging.cpp:62:19: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |  for(int i = 1; i < x.size(); i++) {
      |                 ~~^~~~~~~~~~
Discharging.cpp:68:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   if(i + 1 == x.size())  {
      |      ~~~~~~^~~~~~~~~~~
Discharging.cpp:61:6: warning: unused variable 'ANS' [-Wunused-variable]
   61 |  int ANS = 0;
      |      ^~~

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