제출 #1356381

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1356381		hminhat	Discharging (NOI20_discharging)	C++17	0 / 100	487 ms	1114112 KiB

Discharging

/*	
	ROAD TO TST 
*/
#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define fi first
#define se second
#define pii pair<int, int>
#define el "\n"
#define pb push_back
#define all(v) v.begin(), v.end()

#define rep(i, x, y) for(int i = x, _y = y; i <= _y; i++)
#define rev(i, x, y) for(int i = x, _y = y; i >= _y; i--)

void file() {
	#define name "test"
	if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin);freopen(name".out", "w", stdout);}
	else {
		#undef name
		#define name "C:\\Users\\hminh\\Desktop\\2026\\AIO\\test"
		if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin);freopen(name".out", "w", stdout);}
	}
}

const int nmax = 1e6 + 7;

int n, pos[nmax], up[20][nmax];
ll dp[nmax];

int get(int l, int r) {
	assert(l <= r);
	int k = __lg(r - l + 1);
	return max(up[k][l], up[k][r - (1 << k) + 1]);
}

void update(int i, int j) {
	ll c = dp[i] + 1LL * get(i + 1, j) * (n - i);
	if(dp[j] > c) dp[j] = c, pos[j] = i;
}

void dnc(int l, int r) {
	if(l + 1 == r) return;
	int mid = (l + r) >> 1;

	rep(i, pos[l], pos[r]) {
		update(i, mid);
	}
	dnc(l, mid);
	rep(i, l + 1, mid) {
		update(i, r);
	}
	dnc(mid, r);
}

int main()
{
	file();
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin >> n;
	rep(i, 1, n) {
		cin >> up[0][i];
		dp[i] = 1e18;
	}
	rep(i, 1, __lg(n)) {
		rep(j, 1, n - (1 << i) + 1) {
			up[i][j] = max(up[i - 1][j], up[i - 1][j + (1 << (i - 1))]);
		}
	}
	update(0, n);
	dnc(1, n);
	// cout << dp[n];
	return 0;
}

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

Discharging.cpp: In function 'void file()':
Discharging.cpp:21:44: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin);freopen(name".out", "w", stdout);}
      |                                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Discharging.cpp:21:76: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   21 |         if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin);freopen(name".out", "w", stdout);}
      |                                                                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Discharging.cpp:25:52: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |                 if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin);freopen(name".out", "w", stdout);}
      |                                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
Discharging.cpp:25:84: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   25 |                 if(fopen(name".inp", "r")) {freopen(name".inp", "r", stdin);freopen(name".out", "w", stdout);}
      |                                                                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

• 서브태스크 1: 0 / 9
• 서브태스크 2: 0 / 13
• 서브태스크 3: 0 / 25
• 서브태스크 4: 0 / 11
• 서브태스크 5: 0 / 14
• 서브태스크 6: 0 / 28