Submission #166752

#TimeUsernameProblemLanguageResultExecution timeMemory
166752theStaticMindKrov (COCI17_krov)C++14
70 / 140
1562 ms16544 KiB
#include<bits/stdc++.h> #define mp make_pair #define pb push_back #define ii pair<int,int> #define all(x) (x).begin(),(x).end() #define INF 100000000000000000 #define modulo 1000000007 #define mod 998244353 #define int long long int using namespace std; struct Line{ int M,N; int X,Y; Line(int a,int b,int c,int d){ M=a;N=b;X=c;Y=d; } int get(){ if(M<0){ return M*Y+N; } else return M*X+N; } }; int32_t main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); // freopen("q.gir","r",stdin); // freopen("q.cik","w",stdout); int n,ans=INF; cin>>n; vector<int>arr(n); vector<int>need(n); for(int i=0;i<n;i++)cin>>arr[i]; for(int i=0;i<n;i++)arr[i]--; for(int i=0;i<n;i++){ need[i]=i; } for(int i=n-1;i>=0;i--){ map<int,int>critic; int mn=max((int)0,-(i-(n-i-1))),sum=0; for(int j=0;j<n;j++){ critic[arr[j]-need[j]]++; sum-=need[j]-arr[j]; } int m=-n; vector<Line> data; map<int,int>::iterator pre=critic.begin(),curr; curr=pre; curr++; if(pre->first>=mn)data.pb(Line(m,sum,max((int)mn,(int)-INF),pre->first)); m+=2*pre->second; sum-=2*pre->second*pre->first; while(curr!=critic.end()){ if(curr->first>=mn)data.pb(Line(m,sum,max(mn,pre->first),curr->first)); m+=2*curr->second; sum-=2*curr->second*curr->first; pre++; curr++; } data.pb(Line(m,sum,max(mn,pre->first),INF)); int cnt=INF; for(int j=0;j<data.size();j++){ cnt=min(cnt,data[j].get()); } ans=min(ans,cnt); for(int j=n-1;j>=i;j--){ need[j]-=2; } } cout<<ans; }

Compilation message (stderr)

krov.cpp: In function 'int32_t main()':
krov.cpp:62:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for(int j=0;j<data.size();j++){
                         ~^~~~~~~~~~~~
#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...