제출 #942289

#제출 시각아이디문제언어결과실행 시간메모리
942289LitusianoFeast (NOI19_feast)C++17
51 / 100
1077 ms3932 KiB
#include<bits/stdc++.h> using namespace std; #define int long long const int inf = 1e18; vector<vector<int>> table; int query(int l, int r){ if (l > r) return inf; int len = r-l+1; int k = 63- __builtin_clzll(len); return min(table[l][k], table[r-(1<<k)+1][k]); } signed main(){ ios_base::sync_with_stdio(0); cin.tie(0); int n,k; cin>>n>>k; if(k == 1){ int bst = 0; int cur = 0; for(int i = 0; i<n; i++){ int a; cin>>a; cur = max(0ll, cur+a); bst = max(bst,cur); } cout<<bst<<endl; return 0; } if(n > 3000){ int s = 0; for(int i = 0; i<n; i++){ int a; cin>>a; s+= max(0ll,a); } cout<<s<<endl; return 0; } vector<int> v(n); for(int& i : v) cin>>i; vector<int> pre(n+1); for(int i =0 ; i<n; i++) pre[i+1] = pre[i] + v[i]; table.resize(n+1, vector<int>(25,inf)); for(int i = 0; i<=n; i++) table[i][0] = pre[i]; for(int k = 1; k<25; k++){ for(int i = 0; i<n; i++){ int covers = i + (1<<k) -1; if(covers >= n) break; int nxt = i + (1<<(k-1)); table[i][k] = min(table[i][k-1], table[nxt][k-1]); } } vector<vector<int>> dp(n+1, vector<int>(k+1,0)); // using i with i first, and k customers for(int i = 0; i<=n; i++) dp[i][0] = 0; for(int j = 1; j<=k; j++){ int cur = 0; for(int i = 1; i<=n; i++){ int idx = i-1; dp[i][j] = max(dp[i][j],cur + pre[i]); for(int z = 0; z<i; z++){ // dp[i][j] = max(dp[i][j], dp[z][j] + pre[i] - pre[z]); dp[i][j] = max(dp[i][j], dp[z][j-1] + pre[i] - query(z, i-1)); } cur = max(cur, dp[i][j] - pre[i]); } } int ans = 0; for(int i = 0; i<=n; i++) ans = max(ans, dp[i][k]); cout<<ans<<endl; }

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

feast.cpp: In function 'int main()':
feast.cpp:58:8: warning: unused variable 'idx' [-Wunused-variable]
   58 |    int idx = i-1;
      |        ^~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...