제출 #560103

#제출 시각아이디문제언어결과실행 시간메모리
560103khangal수열 (APIO14_sequence)C++14
71 / 100
624 ms131072 KiB
#include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace __gnu_pbds; using namespace std; typedef long long ll; typedef double db; typedef vector<long long> vl; typedef pair<long long, long long > pl; const int N = 1e6 + 1; #define po pop_back #define pb push_back #define mk make_pair #define lw lower_bound #define up upper_bound #define ff first #define ss second #define boost ios_base::sync_with_stdio(); cin.tie(0); cout.tie(0); #define MOD 1000000007 #define MAX 1e18 #define MIN -1e18 #define per(i,a,b) for(ll i=b;i>=a;i--) #define con continue #define freopen freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout); #define PI 3.14159265358979323846264338327950288419716939937510582097494459230781640628 // typedef tree<ll , null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> indexed_set; // template< typename T> // using indexed_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; ll n, m, mid, res,pos, mn, mx, sum, h1, h2, arr[3234567],arr1[1234567],k, i, j, h, a, x, y, z,par[1234567]; bool used[1234567]; ll tp[1234567]; ll dx[4]={-1,1,0,0},dy[4]={0,0,-1,1},c1[123][123]; //ll jump[22][223456]; //ll lvl[1234567]; //ll bit[1234567]; //ll timer; //ll st[1234567],endd[1234567]; //ll dp[5005][5005]; ll f[2][100010],w[300][200000]; void solve(ll k,ll l,ll r,ll L,ll R){ if(r < l)return; ll mid = (l+r)/2; f[k&1][mid] = MIN; for(int j=L;j<=min(mid,R);j++){ if(f[k&1][mid] < f[k&1^1][j] + arr[j]*(arr[mid] - arr[j]))f[k&1][mid]=f[k&1^1][j] + arr[j]*(arr[mid] - arr[j]),w[k][mid]=j; } solve(k,l,mid-1 , L,w[k][mid]); solve(k,mid+1,r , w[k][mid],R); } class A { public : static void funcA() { cin>>n>>k; f[0][0]=MIN; for(int i=1;i<=n;i++)cin>>arr[i],arr[i]+=arr[i-1]; for(int l=1;l<=k;l++){ solve(l,l,n,l,n); } cout<<f[k&1][n]<<'\n'; vl vec(k); for(int v=n,l=k ; v = w[l--][v];)vec[l]=v; for(auto u:vec)cout<<u<<" "; } }lol; void solve() { A::funcA(); } int main() { ll T = 1; //cin>>T; boost; while (T--) { solve(); } }

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

sequence.cpp: In function 'void solve(ll, ll, ll, ll, ll)':
sequence.cpp:45:29: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   45 |         if(f[k&1][mid] < f[k&1^1][j] + arr[j]*(arr[mid] - arr[j]))f[k&1][mid]=f[k&1^1][j] + arr[j]*(arr[mid] - arr[j]),w[k][mid]=j;
      |                            ~^~
sequence.cpp:45:82: warning: suggest parentheses around arithmetic in operand of '^' [-Wparentheses]
   45 |         if(f[k&1][mid] < f[k&1^1][j] + arr[j]*(arr[mid] - arr[j]))f[k&1][mid]=f[k&1^1][j] + arr[j]*(arr[mid] - arr[j]),w[k][mid]=j;
      |                                                                                 ~^~
sequence.cpp: In static member function 'static void A::funcA()':
sequence.cpp:62:29: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   62 |         for(int v=n,l=k ; v = w[l--][v];)vec[l]=v;
      |                           ~~^~~~~~~~~~~
#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...