Submission #442098

#TimeUsernameProblemLanguageResultExecution timeMemory
442098EvirirFeast (NOI19_feast)C++17
0 / 100
2 ms332 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; #define watch(x) cout<<(#x)<<"="<<(x)<<'\n' #define mset(d,val) memset(d,val,sizeof(d)) #define setp(x) cout<<fixed<<setprecision(x) #define forn(i,a,b) for(int i=(a);i<(b);i++) #define fore(i,a,b) for(int i=(a);i<=(b);i++) #define pb push_back #define F first #define S second #define pqueue priority_queue #define fbo find_by_order #define ook order_of_key typedef long long ll; typedef pair<ll,ll> ii; typedef vector<ll> vi; typedef vector<ii> vii; typedef long double ld; template<typename T> using pbds = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; void amin(ll &a, ll b){ a=min(a,b); } void amax(ll &a, ll b){ a=max(a,b); } void YES(){cout<<"YES\n";} void NO(){cout<<"NO\n";} void SD(int t=0){ cout<<"PASSED "<<t<<endl; } const ll INF = ll(1e18); const int MOD = 998244353; const bool DEBUG = 0; const int MAXN = 300005; int n,K; ll a[MAXN]; ll dp[MAXN], cnt[MAXN]; ii pre[MAXN]; //best dp[j-1]+sum(j..i) for j<=i int main() { ios_base::sync_with_stdio(0); cin.tie(0); freopen("test.in","r",stdin); cin>>n>>K; int pos=0; fore(i,1,n) { cin>>a[i]; if(a[i]>0) pos++; } K=min(K, pos); dp[0]=0; cnt[0]=0; pre[0]={-INF,0}; ll ans=0; for(ll L=0,R=1e16;L<=R;) { ll mid=(L+R)>>1; fore(i,1,n) { ii tmp=pre[i-1]; tmp.F+=a[i]; pre[i]=max(tmp, {dp[i-1]+a[i]-mid, cnt[i-1]+1}); if(pre[i].F>=dp[i-1]) { dp[i]=pre[i].F; cnt[i]=pre[i].S; } else { dp[i]=dp[i-1]; cnt[i]=cnt[i-1]; } } if(cnt[n]>=K) { ans=dp[n]+min((ll)K,cnt[n])*mid; L=mid+1; } else R=mid-1; if(0) { cout<<"mid="<<mid<<'\n'; cout<<"a: "; fore(i,1,n) cout<<a[i]<<" "; cout<<'\n'; cout<<"dp: "; fore(i,1,n) cout<<dp[i]<<" "; cout<<'\n'; cout<<"cnt: "; fore(i,1,n) cout<<cnt[i]<<" "; cout<<'\n'; cout<<"pre: "; fore(i,1,n) cout<<"("<<pre[i].F<<","<<pre[i].S<<") "; cout<<'\n'; cout<<"ans: "<<dp[n]+cnt[n]*mid<<"\n\n"; } } cout<<ans<<'\n'; return 0; }

Compilation message (stderr)

feast.cpp: In function 'int main()':
feast.cpp:43:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   43 |  freopen("test.in","r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
#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...