ABC182
https://atcoder.jp/users/chacoder/history/share/abc182
11月8日21:00-22:40のABC182に参戦しました。
3完でパフォ662、レートは736から7下がって729でした。
このところ単調減少が続いていて心が沈みますが、明日を信じて精進を重ねていきたいと思います。
D問題が解ききれなかったことが反省点。
後日検討するためWAしたコードを挙げておきます。
#include <bits/stdc++.h> using namespace std; long long A[200100]; long long sumA[200100]; long long temp[200100]; int main(){ int n; cin>>n; for(int i=0;i<n;i++){ cin>>A[i]; } sumA[0]=A[0]; for(int i=1;i<n;i++){ sumA[i]=sumA[i-1]+A[i]; } long long maxans=-100000000000000; temp[0]=0; int ck=0; for(int i=0;i<n;i++){ temp[i+1]=temp[i]+sumA[i]; if(temp[i+1]>maxans){ maxans=temp[i+1]; ck=i+1; } } long long ans=temp[ck]; long long finalmaxans=0; for(int i=0;i<=ck;i++){ ans+=A[i]; finalmaxans=max(temp[ck],max(finalmaxans,ans)); } if(ck<n){ ans=temp[ck+1]; for(int i=0;i<=ck+1;i++){ ans+=A[i]; finalmaxans=max(temp[ck+1],max(finalmaxans,ans)); } } if(ck>0){ ans=temp[ck-1]; for(int i=0;i<=ck-1;i++){ ans+=A[i]; finalmaxans=max(temp[ck-1],max(finalmaxans,ans)); } } long long realans=max(max((long long)0,finalmaxans),temp[n]); cout<<realans<<endl; return 0; }
D問題再検討
いろいろ配列をこね回していましたが,他の方の提出をいろいろ見て配列を使わずひとまわしで解けるのがわかりました。
とってもシンプルです。
WAしたコードのどこが悪かったのか原因はつかめていません。
ACしたコード
#include <bits/stdc++.h> using namespace std; #define int long long signed main(){ int n; cin>>n; long long ps=0; long long mx=0; long long cur=0; long long ans=0; long long x; for(int i=0;i<n;i++){ cin>>x; ps+=x; mx=max(mx,ps); ans=max(ans,cur+mx); cur+=ps; } cout<<ans<<endl; return 0; }