답안 #401598

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
401598	2021-05-10T14:40:57 Z	maximath_1	Peru (RMI20_peru)	C++17	컴파일 오류	0 ms	0 KB

peru

#include <bits/stdc++.h>
#include "peru.h"
using namespace std;

#define ll long long
const ll mod = 1e9 + 7;
const ll base = 23;
const ll inf_ll = mod * 2ll * mod + 69ll;
const int MX = 2500005;

ll pwbase[MX];
int n, k, v[MX];
ll dp[MX];
struct dt{
	int id;
	ll dp_id, dp_min;
};
deque<dt> dq;

int vv = 0;
void pop_front(){
	if(dq.size()) dq.pop_front();
	if(dq.size()){
		ll dp_i = dq.front().dp_id;
		dq.front().dp_id = inf_ll;
		dq.front().dp_min = inf_ll;

		for(int i = 1; i < dq.size(); i ++){
			if(dq[i].dp_id <= dp_i) break;
			vv ++;
			dq[i].dp_min = min(dq[i - 1].dp_min, dq[i].dp_id);
		}
	}
}

void push_back(int id){
	if(dq.empty()){
		dq.push_back((dt){id, inf_ll, inf_ll});
		return;
	}

	ll bf = dp[dq.back().id];
	dq.push_back((dt){id, bf + v[id], min(bf + v[id], dq.back().dp_min)});
	return;
}

int solve(){
	for(int i = 0; i < n; i ++){
		if(dq.size() && i - dq.front().id >= k) pop_front();
		while(dq.size() && v[i] >= v[dq.back().id]) dq.pop_back();

		push_back(i);
		dp[i] = (ll)v[dq.front().id];

		if(i >= k) dp[i] += dp[i - k];
		if(dq.size())
			dp[i] = min(dp[i], dq.back().dp_min);
	}

	assert(vv == 0);

	pwbase[0] = 1ll;
	for(int i = 1; i < n; i ++)
		pwbase[i] = (pwbase[i - 1] * 1ll * base) % mod;

	ll ans = 0ll;

	for(int i = 0; i < n; i ++){
		dp[i] %= mod;
		(ans += (pwbase[n - 1 - i] * 1ll * dp[i]) % mod) %= mod;
	}

	return ans;
}

Compilation message

peru.cpp: In function 'void pop_front()':
peru.cpp:28:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::deque<dt>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |   for(int i = 1; i < dq.size(); i ++){
      |                  ~~^~~~~~~~~~~
/usr/bin/ld: /tmp/cc0Fpt8K.o: in function `main':
grader.cpp:(.text.startup+0x144): undefined reference to `solve(int, int, int*)'
collect2: error: ld returned 1 exit status