Submission #80034

#TimeUsernameProblemLanguageResultExecution timeMemory
80034pzdbaDoktor (COCI17_doktor)C++14
80 / 100
1082 ms132096 KiB
#include <bits/stdc++.h> using namespace std; typedef pair<int, int> pii; int a[500005]; int pref[500005], suff[500005]; map<int, map<int, int> > dp; map<int, map<int, pii> > dp2; map<int, map<int, int> >::iterator its2; map<int, int>::iterator its; int main(){ int n; scanf("%d", &n); for(int i=1;i<=n;i++){ scanf("%d", &a[i]); if(i == a[i]) pref[i] = 1; pref[i] += pref[i-1]; } for(int i=n;i>=1;i--){ if(i == a[i]) suff[i] = 1; suff[i] += suff[i+1]; } int ans = 0; for(int i=1;i<=n;i++){ int diff = a[i]-i; if(diff == 0) ans++; int s = 0, e = 0; if(diff < 0) s = i+diff, e = i; else s = i, e = i+diff; int le = e-s+1; diff += 2*i; dp[diff][le]++; dp2[diff][le] = pii(s, e); } int st = a[1], en = a[1]; for(its2 = dp.begin();its2 != dp.end();its2++){ int i = its2->first; int sum = 0; for(its = dp[i].begin();its != dp[i].end();its++){ sum += its->second; int s = dp2[i][its->first].first; int e = dp2[i][its->first].second; if(ans < sum + pref[s-1] + suff[e+1]){ ans = sum + pref[s-1] + suff[e+1]; st = s; en = e; } } } printf("%d %d\n", a[st], a[en]); }

Compilation message (stderr)

doktor.cpp: In function 'int main()':
doktor.cpp:12:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
doktor.cpp:14:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d", &a[i]);
   ~~~~~^~~~~~~~~~~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...