Submission #797678

#	Time	Username	Problem	Language	Result	Execution time	Memory
797678		GoldLight	Rabbit Carrot (LMIO19_triusis)	C++17	100 / 100	23 ms	4156 KiB

triusis

#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]);
      |            ~~~^~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 28 / 28
• Subtask 4: 37 / 37