제출 #654134

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
654134		aebov	Financial Report (JOI21_financial)	C++17	14 / 100	26 ms	14496 KiB

Main

#include<iostream>
#include<algorithm>
#include<vector>
#include<utility>
#define ln (e-s+1)
#define md ((e+s)/2)
#define dm ((e+s)/2 + 1)
#define lc (id*2)
#define rc (id*2 + 1)
#define ll long long
#define F first
#define S second
#define pll pair<ll , ll>
#define pii pair<int, int>
#define pb push_back
using namespace std;

const int N = 7002, inf = (int)1e9 + 7;
int n, d, a[N];
int dp[N][N];
vector<int> vct;
int seg[N][N << 2];

void upd(int k, int p,int x,int id = 1,int s = 1,int e = n){
	if(p < s || p > e)return;
	if(ln == 1){
		seg[k][id] = max(seg[k][id], x);
		return;
	}upd(k , p, x, lc, s, md), upd(k, p, x, rc, dm, e);
	seg[k][id] = max(seg[k][lc], seg[k][rc]);
}
int get(int k,int l,int r,int id = 1,int s = 1,int  e = n){
	if(r < s|| l > e)return -inf;
	if(l <= s && e <= r)return seg[k][id];
	return max(get(k, l, r, lc, s, md), get(k, l, r, rc, dm , e));
}
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	scanf("%d%d", &n,&d);
	for(int i = 1; i <= n; i ++) scanf("%d", &a[i]), vct.pb(a[i]);
	sort(vct.begin(), vct.end()); unique( vct.begin(), vct.end());
	for(int i = 1; i <= n; i ++){
		a[i] = (lower_bound(vct.begin(), vct.end(), a[i]) - vct.begin());
	}
	for(int i = 0; i <= n; i ++)fill(dp[i], dp[i] + N, -inf);
	dp[1][a[1]] = 1; upd(a[1], 1, 1);

	for(int i = 2; i <= n; i ++){
		dp[i][a[i]] = 1; upd(a[i], i, 1);
		for(int k = 0 ; k < a[i]; k ++){
			dp[i][a[i]] = max(dp[i][a[i]] , get(k, max(1,i-d), i-1) + 1);
		}upd(a[i], i, dp[a[i]][i]);
		for(int k = a[i]; k <= n; k ++){
			dp[i][k] = max(dp[i][k], get(k , max(1, i - d), i-1));
			upd(k, i, dp[i][k]);
		}
	}
	int ret = 0;
	for(int i = 0; i <= n; i ++)ret = max(ret, dp[n][i]);
	printf("%d\n", ret);
}

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

Main.cpp: In function 'int main()':
Main.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   39 |  scanf("%d%d", &n,&d);
      |  ~~~~~^~~~~~~~~~~~~~~
Main.cpp:40:36: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   40 |  for(int i = 1; i <= n; i ++) scanf("%d", &a[i]), vct.pb(a[i]);
      |                               ~~~~~^~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 20
• Subtask 4: 0 / 12
• Subtask 5: 0 / 5
• Subtask 6: 0 / 35