Submission #593392

#TimeUsernameProblemLanguageResultExecution timeMemory
593392haojiandan3단 점프 (JOI19_jumps)C++14
46 / 100
395 ms125052 KiB
// wygzgyw #include <bits/stdc++.h> using namespace std; template <typename T> void read(T &t) { t=0; char ch=getchar(); int f=1; while (ch<'0'||ch>'9') { if (ch=='-') f=-1; ch=getchar(); } do { (t*=10)+=ch-'0'; ch=getchar(); } while ('0'<=ch&&ch<='9'); t*=f; } template <typename T> void write(T t) { if (t<0) { putchar('-'); write(-t); return; } if (t>9) write(t/10); putchar('0'+t%10); } template <typename T> void writeln(T t) { write(t); puts(""); } #define MP make_pair typedef long long ll; const int maxn=(5e5)+10; int n,a[maxn]; int q; int st[maxn][20],lg[maxn]; int query(int x,int y) { assert(1<=x&&x<=y&&y<=n); int j=lg[y-x+1]; return max(st[x][j],st[y-(1<<j)+1][j]); } namespace BF { ll mx[5010][5010]; void solve() { for (int len=1;len<=n;len++) for (int i=1,j=len;j<=n;i++,j++) { mx[i][j]=max(mx[i+1][j],mx[i][j-1]); int l=i+1,r=(i+j)>>1; if (l<=r) mx[i][j]=max(mx[i][j],(ll)a[i]+a[j]+query(l,r)); } read(q); while (q--) { int x,y; read(x),read(y); printf("%lld\n",mx[x][y]); } exit(0); } }; namespace Q1 { ll ans; pair<int,int> b[maxn]; void chkmax(ll &x,ll y) { if (x<y) x=y; } void solve() { for (int i=1;i<=n;i++) b[i]=MP(a[i],i); sort(b+1,b+n+1),reverse(b+1,b+n+1); for (int i=1;i<=n&&i<=50;i++) { int x=b[i].second; int l,r; for (int y=x+1;y<=n;y++) { l=y*2-x,r=n; if (l<=r) chkmax(ans,(ll)a[x]+a[y]+query(l,r)); } for (int y=1;y<x;y++) { l=x*2-y,r=n; if (l<=r) chkmax(ans,(ll)a[x]+a[y]+query(l,r)); } for (int y=1;y<x;y++) { l=max(1,y*2-x),r=y-1; if (l<=r) chkmax(ans,(ll)a[x]+a[y]+query(l,r)); } } printf("%lld\n",ans); } }; int main() { //freopen("1.txt","r",stdin); read(n); for (int i=1;i<=n;i++) read(a[i]),st[i][0]=a[i]; for (int i=2;i<=n;i++) lg[i]=lg[i>>1]+1; for (int i=1;i<=19;i++) for (int j=1;j+(1<<i)-1<=n;j++) st[j][i]=max(st[j][i-1],st[j+(1<<(i-1))][i-1]); if (n<=5000) BF::solve(); Q1::solve(); return 0; } /* 0. Enough array size? Enough array size? Enough array size? Integer overflow? 1. Think TWICE, Code ONCE! Are there any counterexamples to your algo? 2. Be careful about the BOUNDARIES! N=1? P=1? Something about 0? 3. Do not make STUPID MISTAKES! Time complexity? Memory usage? Precision error? */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...