제출 #23630

#제출 시각아이디문제언어결과실행 시간메모리
23630SYury수열 (APIO14_sequence)C++11
33 / 100
9 ms4564 KiB
#include<bits/stdc++.h> using namespace std; typedef long long lint; typedef long double ldb; typedef unsigned long long uli; #define X first #define Y second #define F(i, l, r) for(int i = l; i != r; i++) #define Df(i, l, r) for(int i = l; i != r; i--) #define I(i, a) for(auto i : a) #define pb push_back #define rs resize #define mk make_pair #define asg assign #define all(x) x.begin(),x.end() #define ret return #define cont continue #define brk break #define ins insert #define era erase #define fi0(x) memset(x, 0, sizeof(x)) #define finf(x) memset(x, 127, sizeof(x)) #define acpy(y, x) memcpy(y, x, sizeof(y)) #define y1 adjf #define tm dhgdg const int MAXN = 1e3 + 3; const int MAXK = 2e2 + 2; lint dp[MAXN][MAXK]; int pr[MAXN][MAXK]; int a[MAXN]; int ptr[MAXN]; int pref[MAXN]; int n, k; void restore(int i, int j){ if(i < 0)ret; printf("%d ", i + 1); restore(pr[i][j], j - 1); } lint f(int j, int pi, int i){ ret dp[pi][j] + pref[pi] * 1ll * (pref[i] - pref[pi]); } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); scanf("%d%d", &n, &k); F(i, 0, n)scanf("%d", &a[i]); F(i, 0, n)pref[i] = a[i] + ((i == 0) ? 0 : pref[i - 1]); k++; F(i, 0, n) F(j, 1, k + 1) pr[i][j] = -2; dp[0][1] = 0; pr[0][1] = -1; fi0(ptr); F(i, 1, n){ dp[i][1] = 0; pr[i][1] = -1; F(j, 2, k + 1){ while(ptr[j - 1] < i - 1 && (pr[ptr[j - 1]][j - 1] == -2 || f(j - 1, ptr[j - 1], i) <= f(j - 1, ptr[j - 1] + 1, i)))ptr[j - 1]++; if(pr[ptr[j - 1]][j - 1] == -2)cont; dp[i][j] = f(j - 1, ptr[j - 1], i); pr[i][j] = ptr[j - 1]; } } printf("%lld\n", dp[n - 1][k]); restore(pr[n - 1][k], k - 1); ret 0; }

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

sequence.cpp: In function 'int main()':
sequence.cpp:52:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &k);
                       ^
sequence.cpp:53:30: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  F(i, 0, n)scanf("%d", &a[i]);
                              ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...