Submission #797678

#TimeUsernameProblemLanguageResultExecution timeMemory
797678GoldLightRabbit Carrot (LMIO19_triusis)C++17
100 / 100
23 ms4156 KiB
#include <bits/stdc++.h> using namespace std; void fast(){ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);} int main(){ fast(); int n, m; cin>>n>>m; int a[n+1]; a[0]=0; for(int i=1; i<=n; i++){ cin>>a[i]; a[i]=m*i-a[i]; } vector<int> v; for(int i=1; i<=n; i++){ if(a[i]<0) continue; int idx=upper_bound(v.begin(), v.end(), a[i])-v.begin(); if(idx==v.size()) v.push_back(a[i]); else v[idx]=a[i]; } cout<<n-v.size(); } /* const int N=1e5; vector<int> v[N+1]; int lv[N+1]; int main(){ fast(); int n; cin>>n; for(int i=1; i<n; i++){ int x, y; cin>>x>>y; v[x].push_back(y); v[y].push_back(x); } int ans=-1; for(int i=1; i<=n; i++){ if() } } */ /* const int N=24, NN=(1<<24), INF=1e9; int last[NN+1], x[N+1], y[N+1], d[N+1][N+1]; int main(){ fast(); cin>>x[0]>>y[0]; int n; cin>>n; for(int i=1; i<=n; i++) cin>>x[i]>>y[i]; for(int i=0; i<=n; i++){ for(int j=0; j<i; j++){ d[i][j]=d[j][i]=abs(x[i]-x[j])*abs(x[i]-x[j])+abs(y[i]-y[j])*abs(y[i]-y[j]); } } int m=(1<<n); vector<int> dp(NN, INF); dp[0]=0; for(int mask=0; mask<m; mask++){ if(dp[mask]==INF) continue; for(int i=1; i<=n; i++){ if(mask&(1<<(i-1))) continue; for(int j=1; j<=n; j++){ if(mask&(1<<(j-1))) continue; int ii=(1<<(i-1)), jj=(1<<(j-1)); if(dp[mask|ii|jj]>dp[mask]+d[0][i]+d[i][j]+d[j][0]){ dp[mask|ii|jj]=dp[mask]+d[0][i]+d[i][j]+d[j][0]; last[mask|ii|jj]=mask; } } break; } } cout<<dp[m-1]<<'\n'; int bit=m-1; vector<int> ans; while(bit!=0){ int xo=bit^last[bit]; for(int i=0; i<n; i++){ if(xo&(1<<i)) ans.push_back(i+1); } ans.push_back(0); bit=last[bit]; } reverse(ans.begin(), ans.end()); for(auto i:ans) cout<<i<<' '; cout<<0<<' '; } */ /* const int N=24, NN=(1<<24), INF=1e9; int dp[NN+1], last[NN+1], x[N+1], y[N+1]; int main(){ fast(); cin>>x[0]>>y[0]; int n; cin>>n; for(int i=1; i<=n; i++) cin>>x[i]>>y[i]; int m=(1<<n); for(int i=1; i<m; i++) dp[i]=INF; for(int i=1; i<=n; i++){ int add=0; if(n==1) add=abs(x[0]-x[i])*abs(x[0]-x[i])+abs(y[0]-y[i])*abs(y[0]-y[i]); dp[(1<<(i-1))]=abs(x[0]-x[i])*abs(x[0]-x[i])+abs(y[0]-y[i])*abs(y[0]-y[i])+add; last[(1<<(i-1))]=i; } for(int mask=1; mask<m; mask++){ for(int i=1; i<=n; i++){ if(mask&((1<<(i-1)))) continue; for(int j=1; j<=n; j++){ if(!(mask&((1<<(j-1))))) continue; int add=0, nw=mask|(1<<(i-1)); if(nw==m-1){ add=abs(x[0]-x[i])*abs(x[0]-x[i])+abs(y[0]-y[i])*abs(y[0]-y[i]); } if(__builtin_popcount(mask)&1){ int ans=abs(x[i]-x[j])*abs(x[i]-x[j])+abs(y[i]-y[j])*abs(y[i]-y[j]); if(dp[nw]>dp[mask]+ans+add){ dp[nw]=dp[mask]+ans+add; last[nw]=i; } } else{ int ans=abs(x[0]-x[i])*abs(x[0]-x[i])+abs(y[0]-y[i])*abs(y[0]-y[i]); ans+=abs(x[0]-x[j])*abs(x[0]-x[j])+abs(y[0]-y[j])*abs(y[0]-y[j]); if(dp[nw]>dp[mask]+ans+add){ dp[nw]=dp[mask]+ans+add; last[nw]=i; } } } } } //for(int i=1; i<m; i++) cout<<last[i]<<'\n'; cout<<dp[m-1]<<'\n'; vector<int> ans; int temp=m-1; while(temp!=0){ ans.push_back(last[temp]); temp^=(1<<(last[temp]-1)); } reverse(ans.begin(), ans.end()); cout<<'0'<<' '; for(int i=0; i<n; i++){ cout<<ans[i]<<' '; if(i&1 || i==n-1) cout<<'0'<<' '; } } */ /* const int N=3e5; int freq[N+1][26], ans=0; char c[N+1]; bool vis[N+1], to[N+1], cycle=false; set<int> st; vector<int> v[N+1]; void dfs(int node){ if(cycle) return; st.insert(node); freq[node][c[node]-'a']++; vis[node]=true; int frek[26]; memset(frek, 0, sizeof frek); for(auto i:v[node]){ if(st.count(i)){ cycle=true; return; } if(!vis[i]) dfs(i); for(int j=0; j<26; j++) frek[j]=max(frek[j], freq[i][j]); } for(int i=0; i<26; i++){ freq[node][i]+=frek[i]; ans=max(ans, freq[node][i]); } st.erase(node); } int main(){ fast(); int n, m; cin>>n>>m; for(int i=1; i<=n; i++) cin>>c[i]; for(int i=1; i<=m; i++){ int x, y; cin>>x>>y; v[x].push_back(y); to[y]=true; } for(int i=1; i<=n; i++){ if(!to[i]) dfs(i); } for(int i=1; i<=n; i++){ if(!vis[i]){ cycle=true; break; } } if(cycle) cout<<-1; else cout<<ans; } */ /* #define int long long const int N=1e6, mod=1e9+7; int dp[N+1]; signed main(){ fast(); dp[0]=1; int n, a; cin>>n; priority_queue<int> pq; for(int i=1; i<=n; i++){ cin>>a; int root=sqrt(a); for(int j=1; j<=root; j++){ if(a%j==0){ if(j!=a/j){ pq.push(j); pq.push(a/j); } else pq.push(j); } } while(!pq.empty()){ int u=pq.top(); pq.pop(); if(u<=i){ dp[u]=(dp[u]+dp[u-1])%mod; } } } int ans=0; for(int i=1; i<=n; i++) ans=(ans+dp[i])%mod; cout<<ans; } */ /* #define int long long const int N=1e6, mod=998244353; int fact[N+1], inv[N+1]; int expo(int a, int k){ int ret=1; while(k){ if(k&1) ret=ret*a%mod; a=a*a%mod; k/=2; } return ret; } signed main(){ fast(); fact[0]=fact[1]=1; for(int i=2; i<=N; i++) fact[i]=fact[i-1]*i%mod; inv[N]=expo(fact[N], mod-2); for(int i=N-1; i>=0; i--) inv[i]=inv[i+1]*(i+1)%mod; int n; cin>>n; int ans=fact[n]; for(int i=1; i<=n-2; i++) ans=(ans+(fact[n-i]-1)*fact[n]%mod*inv[n-i]%mod)%mod; cout<<ans; } */ /* const int N=1e3, mx=2520; int n, timer, a[N+1], b[N+1], sz[N+1], dp[N+1][mx+1]; vector<vector<int>> v(N+1); int dfs(int x, int y){ if(dp[x][y]>0) return dp[x][y]; if(dp[x][y]<0){ int sum=0; for(int i=1; i<=n; i++){ if(b[i]<=dp[x][y]) sum++; } return dp[x][y]=sum; } dp[x][y]=b[x]=--timer; return dp[x][y]=dfs(v[x][(y+a[x])%sz[x]], (y+a[x])%mx); } int main(){ cin>>n; for(int i=1; i<=n; i++){ cin>>a[i]; a[i]=((a[i]%mx)+mx)%mx; } int x, y; for(int i=1; i<=n; i++){ cin>>sz[i]; for(int j=0; j<sz[i]; j++){ cin>>x; v[i].push_back(x); } } int q; cin>>q; while(q--){ cin>>x>>y; cout<<dfs(x, (y%mx+mx)%mx)<<'\n'; } }*/

Compilation message (stderr)

triusis.cpp: In function 'int main()':
triusis.cpp:17:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |         if(idx==v.size()) v.push_back(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...